How many triangles
Surveyors divide terrain into triangles with vertices at survey points; this is how a terrain model is built. How exactly to draw the triangles is decided by a program, but how many there will be can be said in advance, without building anything.
Given n distinct points of the plane, not all on one line. A triangulation is a division of their convex hull into triangles with vertices at the given points: the triangles do not overlap, together they cover the hull, and no given point lies inside a triangle or on its side other than at a vertex. How many triangles and how many edges does the triangulation have?
The second sample is the 17 fire stations of Almaty; the tests include the city's 7909 street crossings and 45,209 towns of the world (longitude and latitude in thousandths of a degree, coinciding points removed).
Input
The first line holds n (3 ≤ n ≤ 105). Then n lines with integer coordinates x and y of the points (|x|, |y| ≤ 109). All points are distinct and do not lie on one line.
Output
Two numbers: how many triangles and how many edges the triangulation has.
Examples
Example 1
6 0 0 4 0 4 4 0 4 1 2 2 0
5 10
Example 2
17 -1103 -2324 956 2247 1087 2866 -4952 1175 3977 8694 19202 11873 11803 -9089 -5390 -526 6689 12570 -8604 -6793 -6811 771 5915 5067 -1000 6934 -555 10065 -3493 -4205 -6305 8196 3386 603
27 43
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Draw a few small examples. Three points: one triangle and three edges. A square: two triangles and five edges. A square with a point inside: four and eight. What does a point inside change, and what does a point on the boundary change?
2Hint 2
A triangulation is a planar graph, and a planar graph has Euler's formula: vertices minus edges plus faces equals two. A second relation between the numbers comes from counting the sides of the faces: a triangle has three sides, the outer face as many as there are points on the boundary of the hull.
3Hint 3
The answer depends only on n and on the number h of points on the boundary of the convex hull. Not only its corners count, but also points lying on its sides: each of them is a vertex of the outer face. How do you find the hull without losing such points?
4The idea
Let there be T triangles, E edges, and T + 1 faces, the triangles and the outer one. By Euler's formula n − E + T + 1 = 2. Each edge is a side of exactly two faces, and the triangles have 3T sides, the outer face h: 3T + h = 2E. From the two equations T = 2n − 2 − h and E = 3n − 3 − h. The full proof is in the article. The answer is the same for any triangulation: Delaunay, a fan, any other.
5Walkthrough
It remains to find h. Monotone chain: the points are sorted by x, then by y; the lower chain goes from left to right and throws out the last point while the turn is to the right, the upper one from right to left. Points must be thrown out only on a strict right turn and kept on a straight stretch; then the points on the sides of the hull stay in the chains. h is the sum of the chain lengths without the repeated ends.
The first sample: a 4 × 4 square, the point (2, 0) in the middle of the bottom side and the point (1, 2) inside. There are five points on the boundary, h = 5: 2·6 − 2 − 5 = 5 triangles, 3·6 − 3 − 5 = 10 edges. The stations of Almaty have five points of 17 on the hull, giving 27 triangles and 43 edges, and a 250 × 250 grid has 996 points on its boundary.
5+Solution
6Complexity
The sort is O(n log n), the chains O(n): each point goes in and out at most once. There is no need to build the triangulation itself; if you do build it, even the best algorithms are also O(n log n), only with a larger factor.
7Common mistakes
- Only the corners of the hull. A chain that also throws out a point on a straight stretch loses the points on the sides. The answer is wrong already on the first sample, and on the grid by a thousand.
- Only the vertices, without the inner points. Points inside are vertices of the triangulation too: each adds two triangles and three edges.
- Overflow. The cross product with coordinates up to 109 reaches 8·1018: it fits in a signed 64-bit number, but not in a 32-bit one, nor in a double without loss of precision.