MPOLY  Polygon
English  Vietnamese 
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
POLYGON.IN 5 4 2 2 2 2 3 3 2 3 1 POLYGON.OUT 4 POLYGON.IN 8 10 8 3 9 2 8 2 3 9 2 9 10 10 3 8 10 POLYGON.OUT 8 POLYGON.IN 10 9 6 1 7 2 2 3 9 8 7 3 2 9 4 3 1 9 7 6 9 POLYGON.OUT 7 Explanation for test data #2 (coordinates of polygon) 2 8 3 9 8 10 9 10 10 8 10 3 9 2 0 0
hide comments
xxbloodysantaxx:
20160611 20:52:52
I was again and again scanning for POLYGON.IN which is not in the input.


parimala rangan:
20141116 09:52:06
Should we read from the file 'POLYGON.IN' or std::scanf would work? Similarly how should we give the output?


vikas sharma:
20130612 14:43:47
Getting WA in 10th run...:(


legrand:
20121022 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?


farzad abdolhoseini:
20120728 16:13:38
doesn't it mean maximum?


P != NP:
20100427 22:11:55
Almost the same as CVXPOLY and in both problems O(n^4) will get AC 

[Trichromatic] XilinX:
20090417 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:  ~!(*(@*!@^& 
Date:  20090316 
Time limit:  0.111s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COI 01 