MPOLY - Polygon


There are N points in a plane whose coordinates are natural numbers. A convex polygon with maximal number of vertices is a convex polygon whose vertices are some of given points and the origin having maximal possible number of vertices. Origin, i.e. point with coordinates (0, 0), must be one of vertices of a convex polygon with maximal number of vertices.

Write a program that will determine number of vertices in such polygon.

A polygon is convex if every line segment whose endpoints are inside that polygon is also completely inside it. Consecutive edges of a polygon must not be parallel.

Input

The first line of input file contains a natural number N, 2 ≤ N ≤ 100, a number of given points.

Each of the following N lines contains two natural numbers X and Y, 1 ≤ X ≤ 100, 1 ≤ Y ≤ 100, separated by a space character, coordinates of one point.

All points will be different.

Output

The first and only line of output file should contain number of vertices of convex polygon with maximal number of vertices. Note: the result will always be at least 3.

Sample

Input
5
4 2
2 2
2 3
3 2
3 1

Output
4
Input
8
10 8
3 9
2 8
2 3
9 2
9 10
10 3
8 10

Output
8
Input
10
9 6
1 7
2 2
3 9
8 7
3 2
9 4
3 1
9 7
6 9

Output
7

Explanation for test data #2: coordinates of polygon are (2, 8), (3, 9), (8, 10), (9, 10), (10, 8), (10, 3), (9, 2), (0, 0)


hide comments
paroaro: 2018-07-16 14:55:31

autism+tournament s proljevom = AC

Last edit: 2018-07-16 14:58:14
xxbloodysantaxx: 2016-06-11 20:52:52

I was again and again scanning for POLYGON.IN which is not in the input.
I feel very dumb :/

parimala rangan: 2014-11-16 09:52:06

Should we read from the file 'POLYGON.IN' or std::scanf would work? Similarly how should we give the output?

[reply by cyclops: stdin and stdout, just like all other SPOJ problems. Behind the scenes, the judge uses files and pipes.]

Last edit: 2014-11-16 13:58:25
vikas sharma: 2013-06-12 14:43:47

Getting WA in 10th run...:(
any tricky case.....plzzzz someone help...!!!

legrand: 2012-10-22 11:58:10

As the 2 points are aligned with (0,0) and shapes a flat polygon, does the answer for the following input is 3?
2
1 4
2 8

farzad abdolhoseini: 2012-07-28 16:13:38

doesn't it mean maximum?
because the number of vertices in a polygon with maximal number of vertices might not be unique.

Last edit: 2012-07-28 16:14:11
P != NP: 2010-04-27 22:11:55

Almost the same as CVXPOLY and in both problems O(n^4) will get AC

[Trichromatic] XilinX: 2009-04-17 18:38:56

After solving this problem, you may do problem CVXPOLY. That problem is harder than this one and has a strict time limit.


Added by:psetter
Date:2009-03-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 01