题目描述

Cow curling is a popular cold-weather sport played in the Moolympics. Like regular curling, the sport involves two teams, each of which slides N heavy stones (3 <= N <= 50,000) across a sheet of ice. At the end of the game, there are 2N stones on the ice, each located at a distinct 2D point. Scoring in the cow version of curling is a bit curious, however. A stone is said to be "captured" if it is contained inside a triangle whose corners are stones owned by the opponent (a stone on the boundary of such a triangle also counts as being captured). The score for a team is the number of opponent stones that are captured. Please help compute the final score of a cow curling match, given the locations of all 2N stones.

给二维平面n个白点和n个黑点，定义一个点被捕获是在另外一种颜色的某三个点组成的三角形内部(包括边界)，问被捕获的黑白点各有多少

输入格式

Line 1: The integer N.

Lines 2..1+N: Each line contains 2 integers specifying the x and y coordinates of a stone for team A (each coordinate lies in the range -40,000 .. +40,000).

Lines 2+N..1+2N: Each line contains 2 integers specifying the x and y coordinates of a stone for team B (each coordinate lies in the range -40,000 .. +40,000).

输出格式

Line 1: Two space-separated integers, giving the scores for teams A and B.

4 
0 0 
0 2 
2 0 
2 2 
1 1 
1 10 
-10 3 
10 3

1 2 

题目来源

Gold