## Problem G. Great triangle ≡

• problems
 Author: A. Baranov Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

Consider a set of n points on a plane, described by their coordinates: M = {(xi, yi): i = 0, 1, …, n − 1}.

Your program must, given two points A and B, find a point C from set M, such that triangle {A, B, C} contains maximum possible number of points from M. Points both inside and on the edges of the triangle are counted.

### Input file format

Input file contains integer n, followed by n pairs of integers — point coordinates (xi, yi). Next, four integers follow — coordinates of points A and B.

### Output file format

Output file must contain a single integer — index of point C. Indexes start from zero. If there are several solutions, output any of them.

### Constraints

Points A and B are different.

− 104 ≤ (xi, yi) ≤ 104, 0 < n ≤ 105

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
10
-7683 -1465
1000  6970
-1096 -1613
7052  3877
-8237  2965
5089  6152
-7697  5970
1340 -7370
2068  1467
4499 -3269

1990 -5786
-6140 -5000
5
2
10
-4036  1190
4691 -1023
7809 -1023
7021 -6507
4691 -1023
-1000 -5000
3096 -1023
1570 -4210
7809 -1023
7809 -1023

-7500 -5103
-1059 -1023
9

0.089s 0.010s 13