Farmer John's View
Time limit1sMemory limit1024 MB
Given N arcs on a 360-degree circle, each written in degrees, minutes, and seconds, find the total arc-seconds covered by at least one arc.
- Level
Medium4 of 10
- Topics
- Intervals, Sorting, Prefix sum
- Solved
- No attempts yet
Problem
Farmer John wants to leave the dull scenery beside his old farm. He has decided to move from the Wisconsin plains to a new location near the mountains. From there, he looks around in all 360 degrees. Some directions show mountains and others show none. He wants to know what fraction of his view is mountains.
N mountain ranges () surround the new location. Each range appears as a contiguous arc. Think of the view as a circle split into 360 small arcs of 1 degree each. Each degree splits into 60 arc-minutes, and each arc-minute splits into 60 arc-seconds. To record the exact span of each range, Farmer John writes down its starting and ending angles. For example:
Range #34 starts at 45 degrees, 2 minutes, 59 seconds, and ends at 120 degrees, 10 minutes, and 0 seconds.
This description does not say whether the range curves clockwise or counterclockwise. However, no range covers 180 degrees or more, so the direction is unambiguous. The sample range above therefore covers 270,421 arc-seconds. Ranges may overlap. Farmer John wants the total number of arc-seconds in his view that are occupied by mountains.
Input
The first line contains a single integer N.
Each of the next N lines contains 6 space-separated integers. The first three are the degree, minute, and second of the starting angle. The last three are the degree, minute, and second of the ending angle.
Output
Print a single integer: the total number of arc-seconds in the view that are occupied by mountains.
Hint
The first two ranges overlap slightly and cover a combined 270421 arc-seconds. The third range covers 3600 arc-seconds.