#P4793. Treasure Hunt on Happy Island
Treasure Hunt on Happy Island
Treasure Hunt on Happy Island
The game is set on Happy Island where the most famous event is a treasure hunt. Participants are provided with a list of rectangular lands covering the first quadrant. Each rectangle is defined by four coordinates \(x_1, y_1, x_2, y_2\). A rectangle is guaranteed to contain a treasure if there exists at least one other rectangle that completely contains it. Formally, given a rectangle \(R_i = (x_{1}^{(i)}, y_{1}^{(i)}, x_{2}^{(i)}, y_{2}^{(i)})\), it is said to be contained in rectangle \(R_j = (x_{1}^{(j)}, y_{1}^{(j)}, x_{2}^{(j)}, y_{2}^{(j)})\) if \[ x_{1}^{(j)} \le x_{1}^{(i)},\quad y_{1}^{(j)} \le y_{1}^{(i)},\quad x_{2}^{(j)} \ge x_{2}^{(i)},\quad y_{2}^{(j)} \ge y_{2}^{(i)} \] for some \(j \ne i\). Your task is to count the number of rectangular lands that are guaranteed to have a treasure.
inputFormat
The first line contains an integer \(n\) representing the number of rectangular lands. Each of the following \(n\) lines contains four space-separated integers \(x_1\), \(y_1\), \(x_2\), and \(y_2\) representing the coordinates of a rectangle.
outputFormat
Output a single integer representing the count of rectangular lands that are guaranteed to have a treasure, i.e., those rectangles which are contained in at least one other rectangle.
sample
3
1 1 4 4
2 2 3 3
0 0 5 5
2