Cod sursa(job #2121063)

Utilizator flibiaVisanu Cristian flibia Data 3 februarie 2018 11:35:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 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 a[120100], st[120100];
	
double det(point a, point b, point c){
	return (a.x * b.y + b.x * c.y + a.y * c.x - c.x * b.y - b.x * a.y - a.x * c.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 det(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, cmp);
	sort(a + 2, a + N + 1, cmp2);
	st[1] = a[1];
	st[2] = a[2];
	vf = 2;
	for(int i = 3; i <= N; i++){
		while(vf >= 2 && det(st[vf - 1], st[vf], a[i]) > 0)
			vf--;
		st[++vf] = a[i];
	}
	out << vf << '\n';
	out << fixed << setprecision(6);
	for(; vf; vf--)
		out << st[vf].x << ' ' << st[vf].y << '\n';
	return 0;
}