The area inside the fence
The shortest convex fence, the convex hull, has been stretched around points on a plane. How many corners does the fence have, and what is the area inside? Points lying exactly on a side of the fence do not count as corners. To make the answer exact, print twice the area: for integer coordinates it is an integer.
The third test is all earthquakes of magnitude five and above for 2015–2025 from the USGS catalogue, coordinates in hundredths of a degree.
Input
The first line holds n (1 ≤ n ≤ 200,000), then n lines with integer coordinates x, y (|x|, |y| ≤ 10⁹). Points may coincide.
Output
Two numbers: the number of hull vertices and twice its area. If all points are on one line or coincide, the area is 0, and there are 1 or 2 vertices (the extreme points).
Examples
Example 1
9 0 0 4 0 4 3 0 3 2 1 1 2 2 0 4 3 3 1
4 24
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 8 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
The hull is built by the monotone chain from the article. Think about two things: what to do with three points on one line, and whether anything overflows with coordinates up to 10⁹.
2The idea
Build the hull with the condition “≤ 0” in the loop: points on an edge are thrown out, and the answer has only real corners. Twice the area is computed with cross products: a sum of integers, with no division and no fractions.
3Walkthrough
The area is conveniently computed as a “fan” of triangles from the first vertex: 2S = Σ cross(h₀, hi, hi+1). The vertices go counterclockwise, so all terms are positive, and a partial sum never exceeds the final one, at most 2·(2·10⁹)² = 8·10¹⁸. That fits in an int64 (up to 9.2·10¹⁸). The usual shoelace formula with products xi·yi+1 adds terms of different signs, and its partial sums can overflow in Go.
In a cross product each coordinate difference is at most 2·10⁹, a product 4·10¹⁸, the difference of two products 8·10¹⁸: that fits too. Python does not worry about overflow at all.
Edge cases: one point, all points coinciding, all on one line; the hull degenerates into a point or a segment, and the area is zero.
3+Solution
4Complexity
O(n log n) for the sort and O(n) for the pass and the area.
5Common mistakes
- “< 0” instead of “≤ 0”. Points on the sides stay in the hull and are counted as corners. The sixth test is a square with a thousand points on each side.
- The area as a float. Halves and division by two give fractions; twice the area is an integer, and that is what is printed.
- Overflow in Go. The shoelace formula on coordinates of ±10⁹ can overflow a partial sum. A fan from the first vertex cannot.