Aliens! aliens.X
Farmer John's cows are grazing happily in the field. Each of the N (1 <= N
<= 100,000) cows has a unique position, represented by a coordinate pair.
There are also M (1 <= M <= 1,000,000) cow-loving aliens standing in the
field, each with a laser pointer. Each laser pointer emits a ray, and each
alien scans the field with his laser, rotating it clockwise until it points
to a cow. Each laser starts pointing in a direction such that no two cows
are on opposite sides of the laser pointer. That is, at the start, no ray
emitted by an alien's laser intersects the line segment between any two
cows. Each alien has a favorite cow. Write a program for the aliens to tell
them if the first cow seen by each alien will be that alien's favorite cow.
No three cows will lie on the same line, and each alien can determine
exactly which cow he is seeing (i.e. there is only one cow lying on his ray
when he stops scanning the field).
PROBLEM NAME: aliens
INPUT FORMAT:
* Line 1: Two integers separated by a space, N and M, representing the
number of the cows and the number of the aliens.
* Lines 2..N+1: Two integers X and Y (-1,000,000 <= X,Y <= 1,000,000)
representing each cow's position. Cows are numbered with
integers from 1 to N as they appear in the input.
* Lines N+2..N+M+1: Three integers separated by spaces that represent
each alien's position and the number of his favourite cow.
The first two integers are smaller than 10^6 in absolute
value and the third integer is from 1..N.
SAMPLE INPUT:
3 2
0 0
1 0
0 1
1 1 2
2 2 3
OUTPUT FORMAT:
* Lines 1..M: Line number i contain 1 if the the first cow meet by the
laser ray of alien number i is his favourite cow, 0
otherwise.
SAMPLE OUTPUT:
1
0