VMILI  Military Story
Military headquaters plan to develop a better protection for a spaceport. They suppose that the spaceport would be best protected if it is surrounded with as many fences as possible and each fence is patroled by armed guards. The corresponding order was issued and military engineers started to develop a project.
Wishing to be promoted, sergeant Stupid sent soldiers to dig in fence poles before the project was actually ready. Without much thinking, the soldiers put a lot of poles at random. Help the sergeant to decide how to make barbwire fences using the poles so that the number of fences is maximal.
Input
The first line contains an integer 3 ≤ N ≤ 4000, which is the number of the poles. Each of the following N lines contains two integers 0 ≤ x, y ≤ 10000, which are the coordinates of a corresponding pole. No two poles have the same position.
Output
The output should contain a single integer number, which is the maximal possible number of nested fences that can be constructed. Each fence is a closed polygonal line without selfcrossing whose vertices are poles. Different fences should not have common points.
Example
Input: 4 100 100 200 100 100 200 300 300 Output: 1
hide comments
naveenbanda:
20160724 09:03:55
plz provide me any additional test case. I'm getting wrong answer


Archangel:
20150305 03:19:42
AC in first attempt, I thought I might get TLE, thanks for this problem though, I finally was able to implement this task :) 

Mohd Irtefa:
20141031 01:48:52
Does this not work with Python 2.7, I always get a time limit exceeded! 

Naman Goyal:
20140726 14:38:29
Can't understand if the Time Limit is 1s then how did my code get accepted in 1.71s. Is it because judge runs with more than one test case? 

Viktor Fonic:
20131220 09:16:37
Note that when you have 2 poles left, you can't make a fence 

Monkey D. Luffy :
20130320 10:43:24
@Phenomenal more test cases please Last edit: 20130320 10:43:44 

maharaja:
20120121 19:28:26
can someone provide additional testcases


Robin Lee:
20110607 02:15:29
Note to others: "no common points" in this case means no common vertices. Situations where an internal vertex touches an external edge are permissible. 
Added by:  Phenomenal 
Date:  20090216 
Time limit:  0.162s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  acm.timus.ru 