Cod sursa(job #1921133)

Utilizator flibiaVisanu Cristian flibia Data 10 martie 2017 11:30:28
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
#define pdd pair <double, double>
#define x first
#define y second

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int n, cap = 1; pdd a[120100], st[150100];

bool check(pdd a, pdd b, pdd c){
	return (a.x*b.y + b.x*c.y + c.x*a.y) - (c.x*b.y + a.x*c.y + b.x*a.y);
}

bool cmp(pdd b, pdd c){
	return (check(a[1], b, c) < 0);
}

int main(){
	in >> n;
	for(int i = 1; i <= n; i++) in >> a[i].x >> a[i].y;
	sort(a+1, a+n+1);
	st[cap] = a[cap]; cap++;
	sort(a+2, a+n+2, cmp);
	st[cap] = a[cap];
	for(int i = 3; i <= n; i++){
		while(cap >= 2 && check(st[cap-1], st[cap], a[i]) < 0) cap--;
		st[++cap] = a[i];
	}
	out << cap << '\n';
	out << fixed << setprecision(6);
	for(; cap; cap--) out << st[cap].x << ' ' << st[cap].y << '\n';
	return 0;
}