The area of a district in several pieces
A land registry stores the boundary of a plot as a list of points: integer coordinates in metres in its own reference frame. A plot may consist of several separate pieces: the Medeu district of Almaty, besides its main territory, has the Alatau microdistrict, eight kilometres from the rest of the district. The boundary of each piece is a closed ring of points. Rings do not intersect or touch themselves or each other, and none lies inside another: plots have no holes. But the direction of traversal of the rings is arbitrary: as drawn, so stored.
Find the area of each plot, exactly, without rounding. The second test is Almaty’s eight districts from OpenStreetMap in metres on the grid of this catalogue’s road map.
Input
The first line holds the number of plots q (1 ≤ q ≤ 10,000). A plot’s description starts with the number of rings k (k ≥ 1). Each ring is a number of points m (m ≥ 3) and m lines with coordinates x y in order of traversal. All coordinates are integers, |x|, |y| ≤ 10⁹. The input has at most 200,000 points in all.
Output
For each plot, its area in square metres. It is always an integer or a half-integer: print an integer or an integer with .5, without extra zeros.
Examples
Example 1
3 1 4 0 0 4 0 4 4 0 4 1 3 0 0 0 3 1 0 2 4 0 0 4 0 4 4 0 4 3 10 0 10 2 12 0
16 1.5 18
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
First one ring: the shoelace formula in integers gives the doubled area exactly. What does it return for a ring traversed clockwise?
2Hint 2
Take a plot of two squares, one traversed anticlockwise and the other clockwise. What will the shoelace sum over both rings at once give?
3The idea
The shoelace formula gives a signed area: plus for anticlockwise traversal, minus for clockwise. For one ring the absolute value removes the sign. But if the rings are added with signs and the absolute value taken at the end, rings with different directions subtract from each other. The absolute value is taken of each ring separately, and only then added up. The doubled area is an integer, so the answer is either an integer or has a half.
4Walkthrough
For a ring P₀, …, Pm−1 compute 2S = Σ (xi−1yi − xiyi−1), indices taken cyclically. Add |2S| over all rings of the plot in an integer T. The answer: T div 2, with “.5” appended if T is odd.
Exactly this mistake is visible in the article on the Medeu district: the main part of the district is traversed clockwise and gives −267.38 km², the Alatau microdistrict anticlockwise and gives +5.85 km². The absolute value of the signed sum is 261.53 km², while the real area is 273.22 km².
About overflow in Go. Each product is at most 10¹⁸ in absolute value, and the doubled area of a plot within a square of side 2·10⁹ is at most 8·10¹⁸: this fits in int64. Intermediate sums may go over the limit, since a partial shoelace sum is the doubled area of a fan that can wind around the origin several times. But signed integers in Go do not crash on overflow; they wrap around modulo 2⁶⁴ (this is fixed in the language specification). Addition and multiplication modulo 2⁶⁴ agree with ordinary ones, so a final result that itself fits in int64 comes out correct however the intermediate sums wander. The fifth test is a square over the whole field: 4·10¹⁸ m².
4+Solution
5Complexity
O(N), where N is the number of points in the input: one multiply-subtract per side.
6Common mistakes
- The absolute value at the end rather than for each ring. Rings with different directions subtract: this is the wrong solution of the problem. The example and the second test catch it.
- Floating point. With coordinates around 10⁹ a product is about 10¹⁸, while
doubleholds integers exactly only up to 2⁵³ ≈ 9·10¹⁵. The last digits of the answer drift, and a half cannot be told from an integer. The sixth test is small plots right at the edge of the field, where this shows at once. - Printing “12.0” or “12.50”. Exactly “12” or “12.5” is needed: the checker compares strings.