ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Military Story

Time limit: 2.0 second
Memory limit: 64 MB
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.


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.


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 self-crossing whose vertices are poles. Different fences should not have common points.


100 100
200 100
100 200
300 300
Problem Author: Alexey Lakhtin
Problem Source: The Ural State University Championship, October 29, 2005
To submit the solution for this problem go to the Problem set: 1418. Military Story