一、开头
（湖南省神犇协会）
神犇1号：全体神犇，一起去虐HNOI，顺便D一下xyz32768！
（X省Y市）
xyz32768：你们虐完HNOI来干什么啊？不会又要来D人了吧！
神犇256号：哈哈，我们这里有 217 2 17 个柱子，我们想选一些柱子，用这些柱子围成一个凸多边形，并且这个凸多边形必须包含所有的柱子。我会，但我就是不告诉你，就看看你会不会了。
xyz32768：让我想一想………………………………
神犇65536号：如果想不出来的话，我们会随便找一个柱子把你阿掉！
xyz32768：什么？我想不出来了！你们怎么虐完了题还要阿人啊！
神犇1号&神犇256号&神犇65536号&神犇16777216号：我们四个人一起上，把xyz32768阿掉，快追上去！
神犇20号：xyz32768你怎么这么菜啊，凸包多水啊！
二、定义
一个 n n 个点的点集，选出一个子集，这个子集的点能构成一个凸多边形，并且这个凸多边形能覆盖所有的nn个点，那么这个凸多边形就是这 n n 个点的点集的凸包。开头中神犇256号提出的问题就是给定一个217217个点的点集，求这个点集的凸包。给出一个例子：
三、求解
求解凸包的常用算法是Graham扫描法。
先取一个 x x 坐标最小（相同情况下yy坐标最小）的点作为极点，这个点一定在凸包上。
然后把其余的点按照逆时针极角排序（相同情况下按照到极点的距离排序），这一过程可以用叉积实现，不用真正求出极角。即（ O O 为极点，θAθA表示点 A A 的极角）：
θA<θB⇔OA→×OB→>0θA<θB⇔OA→×OB→>0
例（ 1 1 号点为极点，其余的点的编号按照极角大小递增）：
算法实现：用一个栈记录凸包中的点，首先将极点入栈，然后按照逆时针极角大小顺序扫描每个点，扫描到每个点时，
（1）如果栈内的点不足22个，则把这个点加入栈，并结束这一步。
（2）否则设栈顶的点为 Y Y ，栈顶的下一个点为XX，待加入的点为 Z Z ，检查线段XYXY与线段 YZ Y Z 构成的折线段是否拐向右（顺时针方向）（可以用叉积判断，也就是 XY→×XZ→<0 X Y → × X Z → < 0 ），如果满足则退栈，继续检查栈顶的 2 2 个点，直到不满足或者栈中不足22个点为止。
扫描完所有的点之后，栈中剩余的点就是凸包。
由于一个点最多只入栈和出栈一次，因此扫描的复杂度为 O(n) O ( n ) ，但由于极角排序的存在，总复杂度为 O(nlogn) O ( n log n ) 。
四、代码
算法的主体部分非常短。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
int res = ; bool bo = ; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = ; else res = c - ;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << ) + (res << ) + (c - );
return bo ? ~res + : res;
}
const int N = + ;
struct cyx {
int x, y; cyx() {} cyx(int _x, int _y) : x(_x), y(_y) {}
friend inline cyx operator - (cyx a, cyx b) {
return cyx(b.x - a.x, b.y - a.y);
}
friend inline int operator * (cyx a, cyx b) {
return a.x * b.y - a.y * b.x;
}
} a[N]; int n, top, stk[N];
bool comp(cyx x, cyx y) {
int orz = (a[] - x) * (a[] - y);
if (orz != ) return orz > ; if (x.y != y.y) return x.y < y.y;
return x.x < y.x;
}
void solve() {
int i; stk[top = ] = ; for (i = ; i <= n; i++) {
while (top > && (a[stk[top - ]] - a[stk[top]])
* (a[stk[top - ]] - a[i]) < ) top--; stk[++top] = i;
}
}
int main() {
int i, tmp = ; n = read(); for (i = ; i <= n; i++)
a[i].x = read(), a[i].y = read();
for (i = ; i <= n; i++) if (a[i].x < a[tmp].x ||
(a[i].x == a[tmp].x && a[i].y < a[tmp].y)) tmp = i;
if (tmp != ) swap(a[], a[tmp]); sort(a + , a + n + , comp);
solve(); return ;
}
五、题目
（待补充）