1264 - LL’s Fence
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 14
Solved: 6
- Description
- LL has a big block of gold, but he is afraid that someone may still it. So he plans to hide it. LL drives some nails on his territory and plans to build fence between nails. To protect his gold, the fence must be closed, that is a simple polygon in fact. To be more secure, he decides to make many closed fences which are nested one by one (ie. For every two fenced one is nested in the other). But LL has already driven the nails, so he wants to know how to put fences to achieve the maximum number of fences, and hide his gold in the most inner fence.
Note: each nail can only belong to one fence. Not all nails should be used. Two fences can touch but can’t share nails (See sample). - Input
- The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing a integers N (1 <= N <= 1000). Then next N lines each contains two integers —— x and y coordinate of the ith nail(0 <= x, y < 10000 ).
- Output
- For each test case, output a line containing a single integer, the maximum number of fences can be built using the nails.
- sample input
-
2 6 0 0 0 3 1 1 1 2 2 1 3 0 3 0 0 1 1 2 2
- sample output
-
2 0
- hint
- source
- Isun