Cow Curling
Time limit1sMemory limit128 MB
Count the stones of each team that lie inside or on some triangle formed by three opposing stones.
- Level
Medium7 of 10
- Topics
- Geometry, Sorting, Binary search
- Solved
- No attempts yet
Problem
Cow curling is a popular cold weather sport at the Moolympics.
As in ordinary curling, two teams play against each other, and each team slides heavy stones across a sheet of ice (). When the match ends, stones lie on the ice, and all of them sit at distinct points of the plane.
Scoring works in an unusual way. A stone is captured when it lies inside a triangle whose three corners are stones of the opposing team, and a stone on the boundary of such a triangle counts as captured too. The score of a team is the number of opposing stones that are captured.
Given the positions of all stones, compute the final score of the match.
Input
The first line contains the integer .
Each of the next lines contains two integers, the and coordinates of a stone of team A.
Each of the following lines contains two integers, the and coordinates of a stone of team B.
Every coordinate is an integer between and , and the stones sit at distinct points.
Output
Print the score of team A and the score of team B on one line, separated by a space.