Problem E

The Russian navy has, as you probably know, had some problems with their submarines in Swedish waters. These problems are very embarrassing for the Russian military, who has decided to do something about it.

As a first step in their plan, they want to construct a program for their centre of command to be able to locate their submarines.

From GPSes (Global Positioning Systems) they are able to get $X$ and $Y$ coordinates for the front and rear points of all submarines. The Russian intelligence has in addition provided data for all islands in the Swedish waters. With this information, and with a lot of help from simulations using GPS equipped minks, Russian programmers have been able to develop a program that, from the information given, tells the user if a submarine is

  1. Still in water

  2. Partially on land

  3. Entirely on land

The points along the boundaries of the islands are considered to be simultaneously land and water.

\includegraphics[width=0.5\textwidth ]{submarines-fig}
Figure 1: Illustration of sample input


The input consists of:

  • A line with an integer $1 \le n \le 100$, the number of submarines that are present in the area.

  • For each submarine, a line with the $X$ and $Y$ positions first for the submarine’s front and then for its rear.

  • A line with an integer $1 \le m \le 50$, the number of islands in the area.

  • For each island:

    • A line with an integer $3 \le p \le 20$, the number of points of the polygon that represents the island.

    • For each point, a line with the $X$ and $Y$ positions of the point.

All points in the input have coordinates with absolute value bounded by $1000$. The polygons representing the islands are simple (non-self-intersecting) polygons and do not touch or intersect each other.


Output contains information about every submarine, in order.

  1. If the submarine is all in water, print “Submarine $X$ is still in water.

  2. If the submarine is all on land, print “Submarine $X$ is completely on land.

  3. If the submarine is partially in water and partially on land, print “Submarine $X$ is partially on land.

$X$ is the submarine’s number $(1,2,3,\ldots )$ according to its order in the input.

Sample Input 1 Sample Output 1
11 11 9 9
0 0 4 0
0 1 10 1
0 6 6 0
0 -10 0 -9
-5 -5
5 -5
5 5
-5 5
-2 -8
-1 -9
-2 -10
Submarine 1 is still in water.
Submarine 2 is completely on land.
Submarine 3 is partially on land.
Submarine 4 is partially on land.
Submarine 5 is still in water.
Sample Input 2 Sample Output 2
5 0 5 -1
5 10 5 9
0 0
0 10
10 10
10 0
Submarine 1 is partially on land.
Submarine 2 is partially on land.

Please log in to submit a solution to this problem

Log in