#PU1015. USACO 2020 February Contest, Silver — Problem 2. Triangles
USACO 2020 February Contest, Silver — Problem 2. Triangles
USACO 2020 February Contest, Silver — Problem 2. Triangles
题目描述
Farmer John would like to create a triangular pasture for his cows.
There are fence posts () at distinct points
on the 2D map of his farm. He can choose three of
them to form the vertices of the triangular pasture as long as one of the sides
of the triangle is parallel to the -axis and another side is parallel to the
-axis.
What is the sum of the areas of all possible pastures that FJ can form?
输入格式
The first line contains
Each of the next lines contains two integers and , each in the
range inclusive, describing the location of a fence post.
输出格式
As the sum of areas is not necessarily be an integer and may be very large,
数据范围
Test case 2 satisfies
Test cases 3-4 satisfy
Test cases 5-10 satisfy no additional constraints.
样例
样例 1
4
0 0
0 1
1 0
1 2
3
Fence posts $(0,0)$, $(1,0)$, and $(1,2)$ give a triangle of area $1$, while
$(0,0)$, $(1,0)$, and $(0,1)$ give a triangle of area $0.5$. Thus, the answer is
$2\cdot (1+0.5)=3.$
Problem credits: Travis Hance and Nick Wu