首先，什么是凸包？

假设平面上有p0~p12共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”。如下图

然后，什么是凸包问题？ 

我们把这些点放在二维坐标系里面，那么每个点都能用 (x,y) 来表示。 
现给出点的数目13，和各个点的坐标。求构成凸包的点？

时间复杂度：O(n³）。 
思路：两点确定一条直线，如果剩余的其它点都在这条直线的同一侧，则这两个点是凸包上的点，否则就不是。 
步骤：

          1.将点集里面的所有点两两配对，组成 n(n-1)/2 条直线。
           2.对于每条直线，再检查剩余的 (n-2) 个点是否在直线的同一侧。
如何判断一个点 p3 是在直线 p1p2 的左边还是右边呢？（坐标：p1(x1,y1)，p2(x2,y2)，p3(x3,y3)）
 

当上式结果为正时，p3在直线 p1p2 的左侧；当结果为负时，p3在直线 p1p2 的右边。

C++代码实现

#include <bits/stdc++.h>

using namespace std;

const int maxn = 10005;

typedef struct Point
{
    int x;
    int y;
} point;

point p[maxn];
set<pair<int, int> > s;
int n;

int judge(point p1, point p2, point p3)
{
    int flag = p1.x * p2.y + p3.x * p1.y + p2.x * p3.y - p3.x * p2.y - p2.x * p1.y - p1.x * p3.y;
    if (flag > 0) return 1;
    else if (flag == 0) return 2;
    else return 0;
}

int main()
{
    while (cin >> n && n)
    {
        for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;

        s.clear();

        for (int i = 0; i < n; i++)
        {
            int t = 0;

            for (int j = 0; j < n; j++)
            {
                int flag = -1;
                if (i == j) continue;

                for (int k = 0; k < n; k++)
                {
                    if (k == i || k == j) continue;

                    if (flag == -1) flag = judge(p[i], p[j], p[k]);
                    else
                    {
                        int temp = judge(p[i], p[j], p[k]);
                        if (flag == temp || temp == 2) t = 1;
                        else
                        {
                            t = 0;
                            break;
                        }
                    }
                }

                if (t) s.insert(make_pair(p[j].x, p[j].y));
            }

            if (t) s.insert(make_pair(p[i].x, p[i].y));
        }

        set<pair<int, int> >::iterator it = s.begin();

        while (it != s.end())
        {
            printf("(%d, %d)\n", it->first, it->second);
            it++;
        }

    }

    return 0;
}

这里给出2组测试数据

本数据用于临时性检测，明天实验课上会生成更多数据

/*
input1
6
1 3
2 1
4 1
4 3
3 4
6 2

output1
(1, 3)
(2, 1)
(3, 4)
(4, 1)
(6, 2)

input2
14
30 30
50 60
60 20
70 45
86 39
112 60
200 113
250 50
300 200
130 240
76 150
47 76
36 40
33 35

ouput2
(30, 30)
(47, 76)
(60, 20)
(76, 150)
(130, 240)
(250, 50)
(300, 200)
*/