Cod sursa(job #2195723)

Utilizator flibiaVisanu Cristian flibia Data 17 aprilie 2018 11:34:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

struct point{ 
	double x, y;
};

int n, vf;
point P[120100], st[120100];

double delta(point A, point B, point C){
	return A.x * B.y + C.x * A.y + B.x * C.y - C.x * B.y - A.x * C.y - B.x * A.y;
}

bool cmp(point A, point B){
	if(A.x == B.x)
		return A.y < B.y;
	return A.x < B.x;
}

bool cmp2(point B, point C){
	return delta(P[1], B, C) < 0;
}

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