Problem F
Faster Than Light
Faster Than Light (FTL) is a space-based top-down strategy game by Subset Games. You control a ship which belongs to the Galactic Federation and have to fight a ship of the Rebel Faction. The enemies’ spaceship is represented by a set of axis-aligned non-intersecting rectangles in the plane which correspond to the rooms of the ship. Your ship is close to destruction, but your weapon, the hull beam, is ready to fire.
The hull beam shoots an infinite beam in a direction of your choice that deals one damage to each room it intersects. Coincidentally, the enemies’ ship consists of $n$ rooms and has exactly $n$ health points. Thus, you need to hit every room to destroy the enemy before they destroy you. Now you quickly need to check if it is possible to position the beam in such a way. Note that the beam deals damage even when it only touches the boundary of a room. See Figure 1 for an example.
Input
The input consists of:
-
One line with an integer $n$ $(1\leq n \leq 2\cdot 10^5)$, the number of rooms.
-
$n$ lines, each with four integers $x_1$, $y_1$, $x_2$, and $y_2$ (${0\leq x_1<x_2\leq 10^9}$ and ${0\leq y_1<y_2\leq 10^9}$), describing the coordinates of two opposite corners ($x_1$,$y_1$) and ($x_2$,$y_2$) of a room.
It is guaranteed that no two rooms have a common interior point.
Output
If it is possible for the hull beam to pass through all rooms at once, output “possible”. Otherwise, output “impossible”.
Sample Input 1 | Sample Output 1 |
---|---|
5 1 3 3 4 2 2 4 3 4 1 5 3 5 2 7 3 6 3 8 4 |
possible |
Sample Input 2 | Sample Output 2 |
---|---|
4 1 1 2 2 1 3 2 4 3 1 4 2 3 3 4 4 |
impossible |
Sample Input 3 | Sample Output 3 |
---|---|
3 1 1 2 2 1 3 2 4 3 3 4 4 |
possible |