Problem G. Great triangle

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.065s 0.008s 13