BOYSCOUT - Boy Scouts

no tags 

Boy Scouts of New England organize Scout Olympics every year. They ask each team to perform certain tasks, sum up their points, announce winners, and then stay up all night by the fire plying guitar and singing scout songs. This year, Scouts decided to organize the Olympics in one of the most beautiful forests in Maine. There will be only one difficult task. A team picks one tree as a starting point, then goes to another tree in a straight line, then to another, etc. until they come back to the starting one. They win as many points as there are trees on their route. However, they are only allowed to move in a counter-clockwise manner, i.e. after reaching a tree, they can only rotate to the left by less than 180 degrees. Furthermore, when they reach the starting tree again, they should be able to repeat the same route, still going couter-clockwise. More specifically, their path should trace out the boundary of a convex polygon. As they don't bring laptops to the Olympics, the Boy Scouts wants you to compute the maximum possible score a team can achieve.

Input

The first line of the input contains a single integer N (3 ≤ N ≤ 100), which is the number of trees in the forest. Each of the next N lines contain two real numbers x and y separated by a space character (-106 ≤ x, y ≤ 106), that represent coordinates of one tree. Coordinates are given with at most two decimal digits. There are no three colinear trees.

Output

Output one integer, the maximum number of points a team can score, followed by a newline.

Example

Input:
5
0 0
1.5 -0.25
0 -1
-1 0.5
0.5 1

Output:
4

hide comments
sangmai: 2020-09-05 10:14:52

Anyone give some test case?

nadstratosfer: 2018-05-17 10:03:27

In fact, this problem is practically rape. I'm offended by misogyny and hate speech propagated by this far-right website.

komninos: 2018-05-15 20:56:03

This is sexism. Should be gender-neutral scouts


Added by:Minilek
Date:2008-12-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT Individual Contest 2008