凸包模板(去共线)

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
struct node
{
	double x, y;
}a[10005];

int st[10005];


double judge(node p1, node p2, node p0){
	return p1.x * (p2.y - p0.y) + p2.x * (p0.y - p1.y) + p0.x * (p1.y - p2.y);
}

double dist(node p1, node p2){
	return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

void swap(int i, int j){
	node temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

bool cmp(node p1, node p2){
	return judge(p1, p2, a[1]) == 0 ? dist(p1, a[1]) < dist(p2, a[1]) : judge(p1, p2, a[1]) > 0;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%lf %lf", &a[i].x, &a[i].y);
	}
	int k = 1;
	for (int i = 2; i <= n; i++){
		if(a[k].y > a[i].y || (a[k].y == a[i].y && a[k].x > a[i].x)){
			k = i;
		}
	}
	swap(1, k);
	// for (int i = 2; i <= n; i++){
	// 	k = i;
	// 	for (int j = i + 1; j <= n; j++){
	// 		if(judge(a[j], a[k], a[1]) > 0 || (judge(a[j], a[k], a[1]) == 0 && dist(a[j], a[1]) < dist(a[k], a[1]))){
	// 			k = j;
	// 		}
	// 	}
	// 	swap(i, k);
	// }
	sort(a + 2, a + n + 1, cmp);
	int top = 0;
	st[top++] = 1;
	st[top++] = 2;
	st[top++] = 3;
	for (int i = 4; i <= n; i++){
		while(judge(a[i], a[st[top - 1]], a[st[top - 2]]) >= 0) top--;
		st[top++] = i;
	}

	for (int i = 0; i < top; i++){
		printf("%.lf %.lf\n", a[st[i]].x, a[st[i]].y);
	}

	return 0;
}
/**/

/*
6
0 0
3 0
4 0
2 3
2 4
1 1
*/