Processing math: 100%

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,,n1}.

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<n105

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.055s 0.007s 13