Cod sursa(job #1166363)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 3 aprilie 2014 15:07:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <algorithm>
#include <cstdio>
using namespace std;

#define fi first
#define se second

typedef pair<double, double> pdd;
const int MaxN = 120050;
int n;
pdd p[MaxN];

inline double determinant(const pdd &a, const pdd &b, const pdd &c) {
	return a.fi * b.se + b.fi * c.se + c.fi * a.se - a.se * b.fi - b.se * c.fi - c.se * a.fi;
}

int sh, ss;
pdd hull[MaxN], stk[MaxN];
void make_hull() {
	stk[ss = 1] = p[1];
	stk[++ss] = p[2];
	for (int i = 3; i <= n; ++i) {
		while (ss > 1 && determinant(stk[ss - 1], stk[ss], p[i]) < 0)
			--ss;
		stk[++ss] = p[i];
	}
	for (int i = 1; i < ss; ++i)
		hull[++sh] = stk[i];
}

int main() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%lf %lf", &p[i].fi, &p[i].se);
	
	sort(p + 1, p + n + 1);
	make_hull();
	reverse(p + 1, p + n + 1);
	make_hull();
	
	printf("%d\n", sh);
	for (int i = 1; i <= sh; ++i)
		printf("%.6lf %.6lf\n", hull[i].fi, hull[i].se);
}