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