C - Collinearity Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

無限に広い 2 次元平面の上に N 個の点があります。

i 番目の点は (x_i,y_i) にあります。

N 個の点の中の相異なる 3 点であって、同一直線上にあるものは存在するでしょうか？

制約

  • 入力はすべて整数
  • 3 \leq N \leq 10^2
  • |x_i|, |y_i| \leq 10^3
  • i \neq j ならば (x_i, y_i) \neq (x_j, y_j)

入力

入力は以下の形式で標準入力から与えられる。

N
x_1 y_1
\vdots
x_N y_N

出力

同一直線上にある相異なる 3 点が存在するなら Yes を、存在しないなら No を出力せよ。

入力例 1

4
0 1
0 2
0 3
1 1

出力例 1

Yes

(0, 1), (0, 2), (0, 3) の 3 点は直線 x = 0 上にあります。

入力例 2

14
5 5
0 1
2 5
8 0
2 1
0 0
3 6
8 6
5 9
7 9
3 4
9 2
9 8
7 2

出力例 2

No

入力例 3

9
8 2
2 3
1 3
3 7
1 0
8 8
5 6
9 7
0 1

出力例 3

Yes

Score : 300 points

Problem Statement

We have N points on a two-dimensional infinite coordinate plane.

The i-th point is at (x_i,y_i).

Is there a triple of distinct points lying on the same line among the N points?

Constraints

  • All values in input are integers.
  • 3 \leq N \leq 10^2
  • |x_i|, |y_i| \leq 10^3
  • If i \neq j, (x_i, y_i) \neq (x_j, y_j).

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
\vdots
x_N y_N

Output

If there is a triple of distinct points lying on the same line, print Yes; otherwise, print No.

Sample Input 1

4
0 1
0 2
0 3
1 1

Sample Output 1

Yes

The three points (0, 1), (0, 2), (0, 3) lie on the line x = 0.

Sample Input 2

14
5 5
0 1
2 5
8 0
2 1
0 0
3 6
8 6
5 9
7 9
3 4
9 2
9 8
7 2

Sample Output 2

No

Sample Input 3

9
8 2
2 3
1 3
3 7
1 0
8 8
5 6
9 7
0 1

Sample Output 3

Yes