## TLE '17 Contest 6 P4 - Willson and Travelling

View as PDF

Points: 15 (partial)
Time limit: 5.0s
Python 18.0s
Memory limit: 512M
Python 640M
Author:

Problem type

Willson flying around a city while making his presence known.

Willson the Canada Goose is like any other Canada Goose - he likes to fly around and practice honking.

Today, he will be flying around a city containing buildings. Each building is a rectangle with a side parallel to the axis. The lower left corner of the building is at , and the upper right corner is at . A building can overlap with another building. It is possible for a building to be completely contained within another building. Also, it is possible that two different buildings represent the same rectangle.

However, corners are dangerous for Willson to fly into - much more dangerous than walls. A corner is an integer coordinate where exactly of the adjacent squares is contained within a building. The other adjacent squares are not contained within a building.

Could you tell Willson the number of corners that he needs to look out for?

#### Constraints

130All coordinates satisfy .
220All coordinates satisfy .
330All coordinates satisfy .
420All coordinates satisfy .

Note: Python users are recommended to submit with PyPy. Also, Python users are recommended to optimize their memory usage.

#### Input Specification

The first line of input will contain a single integer, .

lines of input follow. The line will contain four integers . The lower left corner of the building is at , and the upper right corner is at . Also, it is guaranteed that and .

#### Output Specification

Output the number of corners that are formed by the buildings.

#### Sample Input

6
1 1 2 2
1 2 2 3
2 2 3 3
6 1 7 4
5 2 8 3
6 2 7 3

#### Sample Output

13

#### Explanation for Sample Output

In the following diagram, the buildings are shown in red and the corners are shown in the black circles.