COCI '16 Contest 5 #3 Unija

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

You are given N rectangles, which are centered in the center of the Cartesian coordinate system and their sides are parallel to the coordinate axes. Each rectangle is uniquely identified with its width (along the x-axis) and height (along the y-axis). The lower image depicts the first sample test.

Mirko has coloured each rectangle in a certain colour and now wants to know the area of the coloured part of the paper. In other words, he wants to know the number of unit squares that belong to at least one rectangle.

Input Specification

The first line of input contains the integer N (1 \le N \le 1\,000\,000), the number of rectangles.

Each of the following N lines contains even integers X and Y (2 \le X, Y \le 10^7), dimensions (width and height, respectively) of the corresponding rectangles.

Output Specification

The first and only line of output must contain the required area.


In test cases worth 40\% of total points, all numbers from the input will be smaller than 3333.

In test cases worth 50\% of total points, not a single rectangle will be located strictly within another rectangle.

Sample Input 1

8 2
4 4
2 6

Sample Output 1


Sample Input 2

2 10
4 4
2 2
8 8
6 6

Sample Output 2



There are no comments at the moment.