#1135. 「USACO 2014.1 Gold」Cow Curling

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
curling.in ≫ curling.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

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.

有两支队伍在比赛,一队可以一次取出3个点来,所围成的三角形覆盖的区域可以“捕获”对方的点,问两支队伍各能够捕获对方多少个点。

输入格式 curling.in

* 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).

输出格式 curling.out

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

样例

输入 #1

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

输出 #1

1 2

数据范围与提示

Each team owns 4 stones. Team A has stones at (0,0), (0,2), (2,0), and (2,2), and team B has stones at (1,1), (1,10), (-10,3), and (10,3).

Team A captures their opponent's stone at (1,1). Team B captures their opponent's stones at (0,2) and (2,2).