ZOJ Problem Set - 3366
You are working in a team developing the new strategic game Island Warriors. The game proceeds on a hexagonal grid, the coordinate system on the map is introduced as shown on the picture below.
A hexagon can be either land, or sea. An island is a maximal connected set of land hexagons, an area of the island is the number of hexagons in it.
Your current task is writing random map generator. The map generated must satisfy some conditions, in particular no island area must exceed s.
The design of your module is the following. Initially all hexagons are sea. Special random generator provides you with the sequence of hexagons. Getting the next hexagon, you check whether it is already the land one. If it is, you just skip this hexagon. If it is sea, you check whether convering it to land results in an island with area exceeding s. If it does, you also skip this hexagon. In the other case you convert it to land.
So, the design step is completed, now its time to implement the module. Fortunately, your teammate has already implemented random generator, so you just have to implement the rest of the module. To check yourself you decided first to output only the number of islands in the resulting map and their areas.
The first line of the input file contains n --- the number of hexagons provided to you by random generator (1 ≤ n ≤ 50000), and s (1 ≤ s ≤ n).
The following n lines contain two integer numbers each --- coordinates of the hexagons. Coordinates do not exceed 500 by their absolute values.
There are multiple cases. Process to the end of file.
Output the number of islands in the resulting map and their areas. List areas in the ascending order.
7 4 0 1 2 1 3 0 1 -1 2 1 1 0 0 0
2 2 3
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #11