ECOO '12 R3 P4 - Splitsville

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

A terrible feud has broken out in the French commune of Lacelle between families that use Android phones (A) and families that use Blackberries (B). Steps need to be taken immediately to keep the two groups apart. We have a map of where everyone lives and an unlimited budget to build electric fences. We don't have time to plan the best possible use of our fences, so we will go with a simple strategy that seems to get pretty good results most of the time.

  1. We will only use fences running North to South (vertical) or East to West (horizontal).
  2. When separating a region of the town, we will build the fence that best separates the houses in that region, creating two new regions. Then we will divide the new regions.
  3. We will continue in this way until every region contains houses of only one family.
  4. When deciding on the "best" fence in a region, we will go with the one that separates at least one house from the others and results in the fewest number of houses on the wrong side of the fence. (A house on the wrong side of the fence is a B house in a majority A area or an A house in a majority B area. If a region has the same number of A and B houses, then the A houses are considered to be on the wrong side.)
  5. If there is a tie for the best fence between horizontal and vertical fences, we will use a horizontal one. If there is a tie among horizontal fences, we will use the northernmost one. If there is a tie among vertical fences, we will use the westernmost one.

These pictures show the result of this fence-building strategy for one possible configuration of houses. Notice that we end up with one fence we don't really need (the third one) but that's the price of a quick and dirty strategy like this.

The input will contain five test cases.

Each test case consists of two lists of X and Y coordinates - one for the Android families, and one for the Blackberry families. Each list starts with the number of items in the list on a single line, followed by the X and Y locations of each house, one per line. The X coordinates are the East-West coordinates, with higher values being more Eastern locations. The Y coordinates are the North-South coordinates, with higher values being more Northern locations. Coordinates are integers ranging from -100\ 000 to +100\ 000.

Your output should consist of one number for each test case representing the number of fences you have to build in order to separate the families, following the strategy described above. The first test case below represents the example pictured above. There will always be at least 1 and at most 200 houses in the village. The maximum width and height of the village is 10\ 000 units. No two houses will ever share the same coordinates.

Sample Input

5
-4 4
-3 2
1 2
-1 -1
0 -4
4
-5 -4
-4 -2
1 -3
3 3
6
-3 4
5 6
2 4
-6 -6
-5 3
0 0
6
0 1
12 4
6 6
-7 -8
3 -5
10 10
10
-1 3
-1 4
-1 6
-1 8
-1 -100
-1 -7
-1 -15
-1 -17
-1 9
-1 -5
2
1 1
1 -1
2
1 1
-1 -1
2
1 -1
-1 1
5
0 3
-2 5
-3 4
-5 6
-7 8
4
-3 5
1 2
2 3
3 4

Sample Output

5
8
1
3
5

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.