[USACO10OPEN]三角形计数Triangle Counting

题目描述

Bessie is standing guard duty after the big bad wolf was spotted stalking ```cpp cows over at Farmer Don's spread. Looking down from her guard tower in utter boredom, she's decided to perform intellectual exercises in ``` order to keep awake. After imagining the field as an X,Y grid, she recorded the coordinates of the N (1 <= N <= 100,000) conveniently numbered 1..N cows as ```cpp X_i,Y_i (-100,000 <= X_i <= 100,000; -100,000 <= Y_i <= 100,000; 1 <= i <= N). She then mentally formed all possible triangles that could be made from subsets of the entire set of cow coordinates. She counts a triangle as 'golden' if it wholly contains the origin (0,0). The origin does not fall on the line between any pair of cows. Additionally, no cow is standing exactly on the origin. Given the list of cow locations, calculate the number of 'golden' triangles that contain the origin so Bessie will know if she's doing a good job. ``` By way of example, consider 5 cows at these locations: -5,0 0,2 11,2 -11,-6 11,-5 Below is a schematic layout of the field from Betsy's point of view: ```cpp ............|............ ............*..........*. ............|............ -------*----+------------ ............|............ ............|............ ............|............ ............|............ ............|..........*. .*..........|............ ............|............ ``` All ten triangles below can be formed from the five points above: By inspection, 5 of them contain the origin and hence are 'golden'. 在一只大灰狼偷偷潜入Farmer Don的牛群被群牛发现后，贝西现在不得不履行着她站岗的职责。从她的守卫塔向下瞭望简直就是一件烦透了的事情。她决定做一些开发智力的小练习，防止她睡着了。 想象牧场是一个X，Y平面的网格。她将N只奶牛标记为1…N (1 <= N <= 100,000)，每只奶牛的坐标为X\_i,Y\_i (-100,000 <= X\_i <= 100,000;-100,000 <= Y\_i <= 100,000; 1 <= i <=N)。然后她脑海里想象着所有可能由奶牛构成的三角形。如果一个三角形完全包含了原点(0,0)，那么她称这个三角形为“黄金三角形”。原点不会落在任何一对奶牛的连线上。另外，不会有奶牛在原点。 给出奶牛的坐标，计算出有多少个“黄金三角形”。

输入输出格式

输入格式

\* Line 1: A single integer: N \* Lines 2..N+1: Each line contains two integers, the coordinates of a single cow: X\_i and Y\_i

输出格式

\* Line 1: A single line with a single integer that is the count of the number of times a triangle formed by the cow locations contains the origin

输入输出样例

输入样例 #1

``````5
-5 0
0 2
11 2
-11 -6
11 -5
``````

输出样例 #1

``````5
``````