961_D. Pair Of Lines_36813
You are given n points on Cartesian plane. Every point is a lattice point (i. e. both of its coordinates are integers), and all points are distinct.

You may draw two straight lines (not necessarily distinct). Is it possible to do this in such a way that every point lies on at least one of these lines?

Input

The first line contains one integer n (1 ≤ n ≤ 105) — the number of points you are given.

Then n lines follow, each line containing two integers xi and yi (|xi|, |yi| ≤ 109)— coordinates of i-th point. All n points are distinct.

Output

If it is possible to draw two straight lines in such a way that each of given points belongs to at least one of these lines, print YES. Otherwise, print NO.

Examples

Input

5
0 0
0 1
1 1
1 -1
2 2


Output

YES


Input

5
0 0
1 0
2 1
1 1
2 3


Output

NO

Note

In the first example it is possible to draw two lines, the one containing the points 1, 3 and 5, and another one containing two remaining points.

<image>
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class P961D
{
	static Point[] ps;
	public static void main(String[] args)
	{
		FastScanner scan = new FastScanner();
		int n = scan.nextInt();
		if (n <= 4)
		{
			System.out.println("YES");
			return;
		}
		ps = new Point[n];
		for (int i = 0; i < n; i++)
			ps[i] = new Point(scan.nextInt(), scan.nextInt());
		if (canDraw(ps[0], ps[1]) || canDraw(ps[0], ps[2]) || canDraw(ps[1], ps[2]))
			System.out.println("YES");
		else
			System.out.println("NO");
	}
	//One line goes through a and b
	private static boolean canDraw(Point a, Point b)
	{
		Line line1 = new Line(a, b);
		ArrayList<Point> other = new ArrayList<>();
		for (Point p : ps)
		{
			if (!line1.pointOnLine(p))
				other.add(p);
		}
		if (other.size() <= 1)
			return true;
		Line line2 = new Line(other.get(0), other.get(1));
		for (Point p : other)
		{
			if (!line2.pointOnLine(p))
				return false;
		}
		return true;
	}
	static class Line
	{
		long a, b, c; // Standard form equation of line: ax + by = c
		Line(Point p1, Point p2)
		{
			a = p1.y - p2.y;
			b = p2.x - p1.x;
			c = a*p1.x + b*p1.y;
		}
		boolean pointOnLine(Point p)
		{
			return a*p.x + b*p.y == c;
		}
	}
	static class Point
	{
		long x, y;
		Point(int a, int b)
		{
			x = a;
			y = b;
		}
	}
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;

		public FastScanner()
		{
			try
			{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
		}

		public String next()
		{
			if (st.hasMoreTokens())
				return st.nextToken();
			try
			{
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return st.nextToken();
		}

		public int nextInt()
		{
			return Integer.parseInt(next());
		}

		public long nextLong()
		{
			return Long.parseLong(next());
		}

		public String nextLine()
		{
			String line = "";
			try
			{
				line = br.readLine();
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return line;
		}
	}
}

5
0 0
0 1
1 1
1 -1
2 2
 5
0 0
1 0
2 1
1 1
2 3
 5
0 0
2 0
1 1
0 2
5 1
 5
0 0
-1 0
-1 1
1 0
1 -1
 8
0 0
1 0
2 0
3 0
0 1
1 1
2 1
3 1
 11
-2 -2
2 3
3 -2
1 -2
2 -2
2 0
2 2
-3 -2
-1 -2
2 -3
2 1
 5
0 0
1 0
0 1
1 1
-1 1
 9
-65536 65536
0 65536
65536 65536
-65536 0
0 0
65536 0
-65536 -65536
0 -65536
65536 -65536
 5
1 1
-1 0
0 1
-1 1
0 0
 4
0 0
-1 1
-1 -1
1 0
 5
3 3
6 3
0 0
10 0
-10 0
 5
-10 3
4 -5
-9 5
-5 -3
-4 -6
 5
0 0
0 1
100 100
100 99
100 98
 5
1000000000 1000000000
999999999 999999999
999999999 999999998
-1000000000 1000000000
-1000000000 999999999
 6
-1 -1
-1 -2
-1 -3
1000000000 1
-1000000000 0
999999999 1
 5
514 2131
312 52362
1 1
2 2
3 3
 6
0 0
0 1
0 2
5 0
5 1
5 -1
 6
1 1
0 0
-1 -1
1 0
0 -1
-1 -10
 7
1 -1
3 -3
1 2
0 -2
1 -3
0 1
0 2
 5
-1000000000 -1000000000
134903170 -298591267
-566505563 -732085704
-298591267 -566505563
-133011126 -464171408
 5
3 0
4 1
0 0
1 1
2 2
 10
0 0
1 0
0 1
0 2
2 0
3 0
0 3
0 4
4 0
0 -10000000
 4
0 0
1 0
0 1
1 1
 5
2 9
-1 -4
-3 -8
-4 8
7 2
 6
0 0
0 1
-1 1
0 -1
1 0
-1 -1
 6
0 0
-1 1
-1 0
1 1
-1 -1
0 -1
 6
0 0
165580141 267914296
331160282 535828592
267914296 433494437
535828592 866988874
433494437 701408733
 7
0 0
2 2
2 -2
-2 2
-2 -2
0 1
0 3
 5
-999999998 -999999998
229254612 -608716103
-588442011 -868997022
-182303375 -739719079
-176884024 -737994046
 4
0 0
0 1
1 0
1 1
 6
0 0
0 1
0 2
1 1
1 2
2 1
 7
0 0
4 0
1 1
2 2
3 1
5 1
6 2
 6
0 -1
1 -1
3 3
2 0
-2 -2
1 -2
 8
0 0
1 0
2 1
1 1
0 1
6 0
5 0
7 0
 5
0 -7
0 10000
1 1000000000
100 0
200 0
 12
0 0
1 1
2 2
3 3
10 11
20 11
30 11
40 11
-1 1
-2 2
-3 3
-4 4
 6
1 1
2 2
3 2
4 1
5 2
6 1
 6
-1 -1
-1 -2
-1 -3
1000000000 1
999999999 1
-1000000000 0
 5
-1 1
1 0
1 1
1 -1
-1 -1
 5
8 8
3303829 10
10 1308
4 2
6 3
 6
-1 -1
-1 -2
-1 -3
0 0
65536 65536
65536 131072
 5
-65536 -65536
65536 0
131072 0
0 65536
0 131072
 5
2 -1
-4 1
0 -9
5 -9
9 -10
 6
0 0
0 1
0 -1
1 1
1 -1
2 -1
 5
1 1
0 0
-1 0
0 1
1 0
 5
-1 2
-1 1
2 1
-2 2
1 1
 5
0 0
0 1
0 2
0 3
1 0
 5
10000000 40000100
3 112
2 400000100
1 104
1000000 701789036
 3
-1 1
-1 -1
0 0
 5
6 1
10 5
10 -2
-2 -10
-4 -9
 1
0 0
 5
0 0
-1 -1
0 -1
-1 1
-1 0
 59
1 0
0 2
0 3
0 4
0 5
6 0
7 0
8 0
9 0
10 0
0 11
12 0
13 0
14 0
15 0
0 16
0 17
18 0
19 0
20 0
21 0
0 22
23 0
24 0
0 25
26 0
27 0
0 28
0 29
30 0
31 0
0 32
33 0
34 0
0 35
0 36
37 0
0 38
39 0
40 0
0 41
42 0
0 43
0 44
0 45
0 46
47 0
0 48
0 49
50 0
0 51
0 52
53 0
0 54
55 0
0 56
57 0
0 58
59 0
 6
0 0
1 1
0 1
1 0
0 2
2 0
 1
-1000000000 1000000000
 5
-1000000000 -1000000000
134903170 -298591267
-566505563 -732085704
-298591267 -566505563
-999999999 -999999999
 10
416 -473
-162 491
-164 488
-170 479
-166 485
-172 476
416 -475
416 -474
-168 482
-160 494
 5
-1000000000 -1000000000
229254610 -608716105
-588442013 -868997024
-182303377 -739719081
-999999999 -999999999
 5
-1000000000 -1000000000
229254610 -608716105
-588442013 -868997024
-182303377 -739719081
-176884026 -737994048
 10
315 202
315 203
315 204
-138 -298
-136 -295
-134 -292
-132 -289
-130 -286
-128 -283
-126 -280
 5
0 0
165580142 267914296
331160283 535828592
267914296 433494437
535828592 866988874
 5
0 0
-1 1
-1 0
0 -1
-1 -1
 10
536870912 536870912
268435456 368435456
268435456 168435456
1 3
2 4
3 5
4 6
5 7
6 8
7 9
 5
0 0
1 1
0 -2
1 -1
1 2
 5
-1000000000 -1000000000
-588442013 -868997024
-182303377 -739719081
-999999999 -999999999
229254610 -608716105
 5
1 -1
0 0
0 1
-1 1
1 1
 6
0 0
2 0
0 2
0 -2
-2 1
-4 2
 6
0 0
1 0
2 1
1 1
0 1
6 0
 5
0 1
2 0
1 1
0 2
5 1
 9
-65536 65536
0 65536
65536 65536
-73920 0
0 0
65536 0
-65536 -65536
0 -65536
65536 -65536
 4
0 0
-1 1
-1 -1
1 -1
 5
3 3
6 3
0 -1
10 0
-10 0
 5
-10 3
4 -8
-9 5
-5 -3
-4 -6
 5
0 0
0 1
100 100
100 99
100 123
 5
1000000000 1000000000
713302725 999999999
999999999 999999998
-1000000000 1000000000
-1000000000 999999999
 6
-1 -1
-1 -2
-1 -3
1000000000 1
-1000000000 0
449435506 1
 5
514 2131
312 52362
1 1
2 2
0 3
 6
1 0
0 1
0 2
5 0
5 1
5 -1
 6
1 1
0 0
-1 -1
1 -1
0 -1
-1 -10
 7
1 -1
3 -4
1 2
0 -2
1 -3
0 1
0 2
 5
-1000000000 -1000000000
134903170 -298591267
-566505563 -414969649
-298591267 -566505563
-133011126 -464171408
 5
3 0
4 1
0 -1
1 1
2 2
 5
2 9
-2 -4
-3 -8
-4 8
7 2
 6
0 0
0 1
-1 1
0 -1
1 0
-2 -1
 6
0 0
165580141 267914296
331160282 535828592
455535293 433494437
535828592 866988874
433494437 701408733
 7
0 0
2 2
2 -2
-2 2
-2 -2
0 1
-1 3
 5
-999999998 -1378788414
229254612 -608716103
-588442011 -868997022
-182303375 -739719079
-176884024 -737994046
 7
0 0
4 0
1 1
0 2
3 1
5 1
6 2
 6
0 -1
1 -1
3 1
2 0
-2 -2
1 -2
 5
0 -7
0 10010
1 1000000000
100 0
200 0
 12
0 0
1 1
2 2
3 3
10 11
20 11
30 11
40 15
-1 1
-2 2
-3 3
-4 4
 6
1 1
2 2
3 2
4 0
5 2
6 1
 6
-1 -1
-1 -2
-1 -3
1000000000 2
999999999 1
-1000000000 0
 5
-1 1
1 0
1 1
2 -1
-1 -1
 5
8 8
2485116 10
10 1308
4 2
6 3
 6
-1 -1
-1 -2
-1 -3
0 0
65536 36421
65536 131072
 5
-65536 -65536
65536 0
131072 0
0 65536
0 87048
 5
2 -1
-4 1
0 -9
5 -9
1 -10
 6
0 0
-1 1
0 -1
1 1
1 -1
2 -1
 5
1 1
0 0
-1 0
-1 1
1 0
 5
-1 2
-1 1
2 1
-4 2
1 1
 5
0 0
0 1
0 4
0 3
1 0
 5
10000000 76667672
3 112
2 400000100
1 104
1000000 701789036
 3
-1 1
0 -1
0 0
 5
9 1
10 5
10 -2
-2 -10
-4 -9
 1
0 1
 5
0 0
-1 -2
0 -1
-1 1
-1 0
 59
1 0
0 2
0 3
0 4
0 5
6 0
7 0
8 0
9 0
10 0
0 11
12 0
13 0
14 0
15 0
0 16
0 17
18 0
19 0
20 0
21 0
0 22
23 0
24 0
0 25
26 0
27 0
0 28
0 29
30 0
31 0
0 32
33 0
34 1
0 35
0 36
37 0
0 38
39 0
40 0
0 41
42 0
0 43
0 44
0 45
0 46
47 0
0 48
0 49
50 0
0 51
0 52
53 0
0 54
55 0
0 56
57 0
0 58
59 0
 6
-1 0
1 1
0 1
1 0
0 2
2 0
 1
-1000000000 1001000000
 5
-1000000000 -1719295120
134903170 -298591267
-566505563 -732085704
-298591267 -566505563
-999999999 -999999999
 10
416 -473
-162 491
-164 488
-170 479
-166 485
-172 476
416 -475
85 -474
-168 482
-160 494
 5
-1000000000 -1000000000
229254610 -608716105
-588442013 -868997024
-182303377 -739719081
-999999999 -435508019
 5
-1000000000 -1000000000
229254610 -608716105
-588442013 -868997024
-29476787 -739719081
-176884026 -737994048
 10
315 202
315 203
315 204
-138 -298
-136 -295
-134 -292
-132 -289
-130 -286
-108 -283
-126 -280
 5
0 -1
165580142 267914296
331160283 535828592
267914296 433494437
535828592 866988874
 5
0 0
-1 1
-1 0
-1 -1
-1 -1
 10
536870912 536870912
268435456 368435456
268435456 168435456
1 3
2 4
3 5
4 6
5 7
6 8
7 6
 5
0 0
1 1
1 -2
1 -1
1 2
 5
-1000000000 -1000000000
-588442013 -868997024
-182303377 -739719081
-1387388513 -999999999
229254610 -608716105
 5
1 -1
0 -1
0 1
-1 1
1 1
 6
0 0
2 0
0 2
0 -2
0 1
-4 2
 5
0 0
0 1
2 1
1 -1
2 2
 5
0 1
2 0
1 1
0 2
5 2
 9
-65536 65536
0 65536
65536 65536
-73920 0
0 0
65536 0
-65536 -65536
0 -65536
65536 -64563
 4
-1 0
-1 1
-1 -1
1 -1
 5
3 5
6 3
0 -1
10 0
-10 0
 5
-10 3
4 -8
-9 5
-5 -2
-4 -6
 5
0 0
0 1
100 100
000 99
100 123
 5
1000000000 1100000000
713302725 999999999
999999999 999999998
-1000000000 1000000000
-1000000000 999999999
 6
-1 -1
-1 -2
-1 -3
1000000000 1
-1000000000 0
449435506 0
 5
514 2131
312 52362
1 1
1 2
0 3
 6
1 0
0 1
0 2
5 0
5 1
5 -2
 6
1 1
0 0
-1 0
1 -1
0 -1
-1 -10
 7
1 0
3 -4
1 2
0 -2
1 -3
0 1
0 2
 5
-1000000000 -301105775
134903170 -298591267
-566505563 -414969649
-298591267 -566505563
-133011126 -464171408
 5
3 0
4 1
0 -1
1 1
2 1
 5
2 9
0 -4
-3 -8
-4 8
7 2
 6
0 0
0 1
-1 0
0 -1
1 0
-2 -1
 6
0 0
165580141 267914296
331160282 535828592
455535293 162343203
535828592 866988874
433494437 701408733
 7
-1 0
2 2
2 -2
-2 2
-2 -2
0 1
-1 3
 5
-999999998 -1378788414
229254612 -608716103
-588442011 -868997022
-182303375 -739719079
-307533159 -737994046
 6
0 -1
1 -1
3 0
2 0
-2 -2
1 -2
 5
0 -7
0 10010
1 1000000000
100 0
200 1
 12
0 0
1 1
2 2
3 3
10 11
20 0
30 11
40 15
-1 1
-2 2
-3 3
-4 4
 6
1 1
0 2
3 2
4 0
5 2
6 1
 6
-1 -1
-1 -4
-1 -3
1000000000 2
999999999 1
-1000000000 0
 5
8 8
2485116 10
10 1308
4 2
6 5
 5
-65536 -65536
65536 0
131072 0
0 56008
0 87048
 5
3 -1
-4 1
0 -9
5 -9
1 -10
 6
0 0
-1 1
0 -1
1 1
1 0
2 -1
 5
1 1
0 0
-1 0
-1 1
2 0
 5
-1 2
-1 1
2 1
-5 2
1 1
 5
10000000 76667672
3 112
2 400000100
2 104
1000000 701789036
 3
-2 1
-1 -1
0 0
 5
9 2
10 5
10 -2
-2 -10
-4 -9

YES
 NO
 YES
 YES
 YES
 YES
 YES
 NO
 YES
 YES
 YES
 NO
 YES
 NO
 NO
 YES
 YES
 NO
 NO
 YES
 YES
 YES
 YES
 NO
 NO
 NO
 NO
 NO
 YES
 YES
 NO
 NO
 NO
 YES
 NO
 NO
 YES
 NO
 YES
 NO
 NO
 NO
 NO
 NO
 YES
 YES
 YES
 YES
 YES
 YES
 YES
 YES
 YES
 NO
 YES
 NO
 YES
 NO
 YES
 YES
 YES
 YES
 NO
 YES
 NO
 YES
 NO
 YES
 YES
 NO
 YES
 NO
 NO
 YES
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 YES
 YES
 YES
 NO
 YES
 NO
 YES
 YES
 NO
 NO
 YES
 NO
 NO
 NO
 YES
 NO
 NO
 YES
 NO
 YES
 NO
 YES
 YES
 NO
 YES
 NO
 YES
 NO
 NO
 YES
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 YES
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 YES
 NO
 NO
 NO
 YES
 YES
 NO
 YES
 NO
