Inverted Triangles
InterviewTime limit2sMemory limit1024 MB
Given N points, find the sum of doubled areas of all inverted triangles, where the middle-x point has the lowest y, modulo 1000000007.
- Level
Medium6 of 10
- Topics
- Sorting, Prefix sum, Geometry
- Solved
- No attempts yet
Problem
On an infinite two-dimensional coordinate plane, there are points. The points are numbered from to , and the coordinates of point are . All point coordinates are distinct.
Choose three distinct numbers , , and between and inclusive. Connecting the points for these numbers with line segments forms a triangle. A triangle that satisfies all of the following conditions is called an inverted triangle.
- .
- .
- .
Let be the sum of the areas of all inverted triangles that can be formed by choosing three points. Print the remainder when is divided by (= ). It can be proven that is always an integer.
Input
The first line contains . ()
Each of the next lines contains two integers and , separated by a space. ()
Output
Print the remainder when is divided by . This number is prime.