시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 393 | 96 | 73 | 32.159% |
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.
4 0 0 0 2 2 0 2 2 1 1 1 10 -10 3 10 3
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).
Olympiad > USA Computing Olympiad > 2013-2014 Season > USACO January 2014 Contest > Gold 1번