Cod sursa(job #605099)

Utilizator S7012MYPetru Trimbitas S7012MY Data 26 iulie 2011 18:51:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#define DN 120005
using namespace std;

int n,ind[DN],stk[DN],p;
double x[DN],y[DN];

bool det(int i1, int i2,int i3) {
	return(x[i1]*y[i2]+x[i2]*y[i3]+x[i3]*y[i1]-
		   y[i1]*x[i2]-y[i2]*x[i3]-y[i3]*x[i1]
	)<=0;
}

bool cmp(int a, int b) {
	return (y[a]-y[p])*(x[b]-x[p])<(y[b]-y[p])*(x[a]-x[p]);
}

int main()
{
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	f>>n;
	for(int i=1; i<=n; ++i) {
		f>>x[i]>>y[i];
		ind[i]=i;
	}
	
	int sz;
	p=1;
	sort(ind+1,ind+n+1,cmp);
	stk[++sz]=1;
	for(int i=1; i<=n; ++i) {
		for(;sz>=2 && det(stk[sz-1],stk[sz],ind[i]);--sz);
		stk[++sz]=ind[i];
	}
	for(int i=1; i<=sz; ++i) g<<fixed<<setprecision(6)<<x[stk[i]]<<' '<<y[stk[i]]<<'\n';
	return 0;
}