Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2856.   Serious Cow Tag
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 879   Accepted Runs: 312    Multiple test files



Farmer John's N (1 ≤ N ≤ 1000) cows (conveniently numbered 1..N) are going to play a game of Serious Cow Tag. In Serious Cow Tag, each cow chooses a grid point in the pasture (-7500 ≤ X ≤ 7500, -7500 ≤ Y ≤ 7500) such that the distances between all pairs of cows are unique.

The cows play in turn, starting with cow #1 and continuing with cows #2, #3, and so on (as long as the cow is still in the game). When it is a cow's turn to play, she finds the nearest cow still playing, ambles over to that cow to tag her, and then returns to her original location. As soon as a cow is tagged, she is out of the game.

The game ends when only one cow remains, and she is declared the winner.

Farmer John is taking bets with neighboring farmers as to which cow will win, so he would like to know the winner in advance. Write a program that will read a description of the cows' positions and determine the winner.

Input

* Line 1: A single integer N, the number of cows

* Lines 2..N + 1: Line i+1 contains two space-separated integers that describe the location of cow i.

Output

* Line 1: The number of the winning cow.

Sample Input

3
0 0
0 3
4 3

Sample Output

3

Input Details

Three cows at (0, 0), (0, 3) and (4, 3).

Output Details

Cow 1 goes first and tags the nearest cow, cow 2. Cow 2 is eliminated so she does not get a turn. Cow 3 then tags the only remaining cow, cow 1. She is the last cow left, so she wins.


Source: USACO 2006 November Competition
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz