首页 > ACM题库 > HDU-杭电 > hdu 2271 The Biggest Convex Hall待解决[解题报告]C++
2014
01-04

hdu 2271 The Biggest Convex Hall待解决[解题报告]C++

The Biggest Convex Hall

问题描述 :

If you are fond of ACM , you must have know the word “Convex Hall ” . which can forms a convex polygon .
Now we define the size of a convex hall as the number of edges it contains .
Give you several points , you can choose some points to form a Convex Hall .Can you tell me the biggest size of convex hall you may find?
What’s more , the convex hall must contains the point (0,0).

输入:

Each test case will contains an integer n (2<= n<= 100 ), which stands for the number of points you are given besides (0,0).
Then n lines follow. Each line contains two integers x and y ( 0<=x, y <=100) , mean the coordinate of the point .
You may suppose you can at least find a convex hall with 3 edges.

输出:

Each test case will contains an integer n (2<= n<= 100 ), which stands for the number of points you are given besides (0,0).
Then n lines follow. Each line contains two integers x and y ( 0<=x, y <=100) , mean the coordinate of the point .
You may suppose you can at least find a convex hall with 3 edges.

样例输入:

4
0 1
1 0
0 2
2 0

样例输出:

3


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环