Triangles (Silver)
InterviewTime limit1sMemory limit512 MB
Given N points, sum twice the areas of all right triangles whose legs are parallel to the axes, modulo 1e9+7.
- Level
Medium6 of 10
- Topics
- Math, Geometry, Combinatorics, Hash map
- Solved
- No attempts yet
Problem
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?
Input
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.
Output
As the sum of areas is not necessarily an integer and may be very large, output the remainder when two times the sum of areas is taken modulo .
Hint
Fence posts , , and give a triangle of area , while , , and give a triangle of area . Thus, the answer is .