Subscribed unsubscribe Subscribe Subscribe

stkblog

白血病と関係ないことを書きます なにかあったら教えて下さい

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

Codeforces python

問題

codeforces.com

n本の1次関数のグラフが区間  {\textstyle (x_1, x_2) } で交点を持つかどうか。

はじめに思ったこと

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

次に思ったこと

  •  {\textstyle f(x_1) , f(x_2) } を計算して大小関係を調べようかなあ
  • これ 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 でフィルタすると交点求めてるのが多いような。

交点を求めると  {\textstyle \rm _n C _2 } 回計算するから n が大きくなると間に合わない?
この解法だと  {\textstyle  2n + (n -1) + n \log n } だからセーフ?ってこと?かな?
ソートしたのがよかったのかな(よく考えてなかったけど

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

codeforces.com

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