Line of Sight
Time limit1sMemory limit128 MB
Count the pairs of N points outside a central circle whose connecting segment avoids the circle.
- Level
Medium7 of 10
- Topics
- Geometry, Sorting, Two pointers
- Solved
- No attempts yet
Problem
Farmer John's cows stand at distinct points of his pasture. A large round grain silo sits in the middle of the pasture. Cows on opposite sides of the silo cannot see each other because the silo blocks the view. Count the pairs of cows that can see each other.
Seen from above, the silo is a circle of radius centered at the origin . Two cows can see each other when the segment joining them does not meet this circle, and cannot when it does.
No cow stands inside the circle or on it, and no line through two cows is tangent to the circle.
Input
The first line has the number of cows and the silo radius (, ).
Each of the next lines has the coordinates and of one cow (). All input values are integers.
Output
Print the number of pairs of cows that can see each other.
Hint
In the first example four cows stand at , , and around a silo of radius . There are six ways to pick two of the four cows, and the two pairs that face each other across the silo cannot see each other: with , and with . The other four pairs can see each other.