## HCI '16 - Moana

View as PDF

Points: 15 (partial)
Time limit: 0.3s
Memory limit: 64M

Authors:
Problem type

#### Problem Description

Moana is the story of a Polynesian girl of the same name who, together with the demigod Maui, defy impossible odds to save her people.

Having done so, she now leads her people to discover new islands in the Pacific to settle, in line with their historical tradition of voyaging. During the expeditions, she discovers islands, as well as tiles of pirate ship enclaves, within a space of by . Polynesian islands are generally very small, and as such occupies one tile each. Pirate enclaves occupy a single tile in the sea, but coming closer than tiles of any of them (excluding the pirate tile) will put a ship within sight, prompting the pirates to attack. Land and pirate tiles will never coincide, and pirates do not have the military and logistical capability to assault a beachhead assault on islands within their sight.

Having settled all islands, Moana now wants to set up a network of safe sailing routes that connects all the islands to promote trade, visiting, and cultural exchanges. To be safe, the routes must not be under any threat from pirates. Since the Polynesians have perfected the art of wayfinding, being able to read the stars, the sun, and the ocean's swells to navigate, sailing routes can extend infinitely, traversing the deepest oceans and crossing the stormiest seas.

A sailing route consists of an unbroken chain of ocean tiles connected in any of the four cardinal directions. It begins from any point on one island and ends on any point of another. A patrol sailboat will then be dispatched to guard each tile of the routes to protect the vital sea lanes. Intersections between sailing routes will have additional patrol sailboats deployed, equal to the number of routes involved in the intersection, as it is a more likely area of attack. Since resources are limited, help Moana find out what is the minimum number of patrol sailboats that must be built for this purpose!

#### Input

The first line contains five integers, .

The next lines contain two integers each, the and coordinates of each island.

Subsequent lines contain two integers each, the and coordinates of the pirate enclaves.

#### Output

The output should only consist of one integer, the minimum number of patrol sailboats that must be built to connect all islands. If it is impossible to connect all islands, output .

#### Constraints

Islands are distributed in a checkerboard pattern, with the first grid always being occupied.

#### Sample Input

4 0 0 4 5
1 2
2 3
3 4
4 1

#### Sample Output

5

#### Explanation for Sample Output

The image above shows a grid with island tiles denoted in brown and ocean tiles in blue. A possible deployment that utilizes the minimum number of boats to secure connections between all islands is shown.

• commented on Jan. 23, 2020, 1:31 a.m.

This question is sort of confusing. It says:

Pirate enclaves occupy a single tile in the sea, but coming closer than S tiles of any them (excluding the pirate tile) will put a ship within sight, prompting the pirates to attack.

Can this be elaborated on?