ZOJ Problem Set - 3234
A crowd of people are planning to kill the King, who has been tyrannical for years. The King asks a group of soldiers to protect him. The soldiers stand on the ground, but NO three or more soldiers stand in a single line and NO two of them are at the same point. Each two of them can connect themselves with an iron chain. When some soldiers connect themselves in a CLOSED iron chain circle, a circle of protection is formed. The soldiers can form one, two or more circles, and the King will stand inside all circles of protection, so that it's difficult for the people to break in. The picture below shows an example of "two circles of protection", the red circle indicating the supposed position of the King.
However, when iron chains of different protection circles cross each other, there may well be a chaos when the people try to break in, so it's NOT allowed that chains of different protection circles cross each other. Of course, the more circles of protection, the safer the King. Now given the coordinates of the soldiers, you are asked to calculate the maximal number of protection circles that can form.
There are multiple cases(no more than 25). In each case, there's an integer n ( 2 < n <= 2000) in the first line, indicating the number of soldiers. The second line includes n pairs of integers xi, yi ( 0 <= xi, yi < 100000), indicating the position of the ith soldier.
Print the maximal number of protection circles that can form in one line for each case.
4 0 0 0 1 1 0 1 1 8 0 0 8 0 8 3 0 3 2 1 2 2 3 2 3 1
Author: SHE, Jieying
Source: ZOJ Monthly, August 2009