otoczka 2

#include <cstdio>
#include <functional>
#include <algorithm>
#include <math.h>
#include <queue>

using namespace std;

struct point {
	int x;
	int y;
};
point P1;
point *tab;

int iloczyn(point a, point b, point c) {
	int area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
	return area; //if >0 c is on the left of AB
}

int dist(point O, point P) {
	int x = P.x - O.x; int y = P.y - O.y;
	return x*x + y*y;
}

bool comp(point a, point b) {
	int dot_product = iloczyn(tab[0], a, b);
	return (dot_product > 0 || (dot_product == 0 && dist(tab[0], a) < dist(tab[0], b)));
}

int main() {
	int n;		scanf("%d", &n);

	tab = new point[n];

	int x, y;		scanf("%d %d", &x, &y);		 tab[0].x = x; tab[0].y = y;

	//////////////////////////////////////
	for (int i = 1; i < n; i++) {
		scanf("%d %d", &x, &y);
		tab[i].x = x; tab[i].y = y;
		if (tab[i].y < tab[0].y || (tab[i].y == tab[0].y && tab[i].x < tab[0].x)) {
			swap(tab[i], tab[0]);
		}
	}

	sort(tab + 1, tab + n, comp);

	vector<point> otoczka;
	otoczka.push_back(tab[0]);
	otoczka.push_back(tab[1]);

	for (int i = 2; i < n; i++) {
		point B = otoczka.back();
		otoczka.pop_back();
		while (otoczka.size() > 0 && iloczyn(otoczka.back(), B, tab[i]) <= 0) {
			B = otoczka.back();
			otoczka.pop_back();
		}
		otoczka.push_back(B);
		otoczka.push_back(tab[i]);
	}
	otoczka.push_back(tab[0]);
	//////////////////////////////////////

	while (!otoczka.empty()) {
		printf("%d %d\n", otoczka.back().x, otoczka.back().y);
		otoczka.pop_back();
	}
	return 0;
}
//@author Tooster
/*
5
1 1
1 2
2 3
3 2
2 1

6
1 1
2 3
3 5
4 1
2 1
3 2
*/