Codeforces#329 B問題 - Anton and Lines やってみた

問題

codeforces.com

n本の1次関数のグラフが区間 で交点を持つかどうか。

はじめに思ったこと

交点のx座標を全部求めようかなあ

次に思ったこと

• を計算して大小関係を調べようかなあ
• これ n が大きいと TLE (Time Limit Exceeded) になるやつかなあ*1

書いた

#!/usr/bin/python
# -*- coding: utf-8 -*-
N = input()
x1, x2 = map(int, raw_input().split())

ys = []
for loop in xrange(N):
    k, b = map(int, raw_input().split())
    y1 = k * x1 + b
    y2 = k * x2 + b
    ys.append((y1, y2))

ys = sorted(ys)
# 関数の区間の端でのy座標 (y1, y2) のリストを y1 でソート

for i in xrange(len(ys)-1):
    if ys[i][1] > ys[i+1][1]:
        print 'YES'
        break
else:
    print 'NO'

# y2 もソートされた状態になってたら交点がない

Accepted いぇーい

おわり

Accepted でフィルタしたところ、似たような解法が並んでるのでこれでよかったっぽい。
TLE でフィルタすると交点求めてるのが多いような。

交点を求めると 回計算するから n が大きくなると間に合わない？
この解法だと だからセーフ？ってこと？かな？
ソートしたのがよかったのかな（よく考えてなかったけど

まあできたのでよかったですおわり

codeforces.com

*1:計算量とかそういうのいまいちわかってない