Author: | A. Baranov | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
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 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 must contain a single integer — index of point C. Indexes start from zero. If there are several solutions, output any of them.
Points A and B are different.
−104≤(xi,yi)≤104, 0<n≤105
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|