## 2014年1月31日

### UVa 11626 - Convex Hull

```#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct P {

P (long long x, long long y) : x(x), y(y) {
}

bool operator < (const P & other) const {
return x != other.x ? x < other.x : y < other.y;
}

P operator - (const P & other) const {
return P(x - other.x, y - other.y);
}

long long operator ^ (const P & other) const {
return x * other.y - y * other.x;
}

long long x, y;
};

int orient(P & p1, P & p2, P & p3) {
long long area = (p2 - p1) ^ (p3 - p1);
return area == 0 ? 0 : area > 0 ? 1 : -1;
}

int main() {
int T;
scanf("%d", &T);
while (T--) {
int N;
scanf("%d", &N);
vector<P> points;
while (N--) {
long long x, y;
char temp[99];
scanf("%lld%lld%s", &x, &y, temp);
points.push_back(P(x, y));
}
sort(points.begin(), points.end());
vector<P> ch[2];
ch[0].push_back(points[0]);
ch[0].push_back(points[1]);
for (int i = 2; i < points.size(); i++) {
ch[0].push_back(points[i]);
while (ch[0].size() >= 3 && orient(points[i], ch[0][ch[0].size() - 2], ch[0][ch[0].size() - 3]) > 0) {
ch[0].pop_back();
ch[0].pop_back();
ch[0].push_back(points[i]);
}
}
ch[1].push_back(points[points.size() - 1]);
ch[1].push_back(points[points.size() - 2]);
for (int i = points.size() - 3; i >= 0; i--) {
ch[1].push_back(points[i]);
while (ch[1].size() >= 3 && orient(points[i], ch[1][ch[1].size() - 2], ch[1][ch[1].size() - 3]) > 0) {
ch[1].pop_back();
ch[1].pop_back();
ch[1].push_back(points[i]);
}
}
vector<P> ans;
for (int i = 0; i < ch[0].size(); i++) {
ans.push_back(ch[0][i]);
}
for (int i = 1; i < ch[1].size() - 1; i++) {
ans.push_back(ch[1][i]);
}
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++) {
printf("%lld %lld\n", ans[i].x, ans[i].y);
}
}
return 0;
}
```