Cod sursa(job #680813)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 15 februarie 2012 22:31:13
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<vector>
#define lim 120002
using namespace std;
double x[lim],y[lim];
int IndicePunctCurent,IndicePunctPlecare,pozitie,n,i;
bool verif,viz[lim];
double u,maxu,unghi;
vector<int>a;
int main (){
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lf%lf",&x[i],&y[i]);
	IndicePunctPlecare=1;
	for(i=2;i<=n;i++){
		if(x[IndicePunctPlecare]>x[i])
			IndicePunctPlecare=i;
	}
	IndicePunctCurent=IndicePunctPlecare;
	u=0;
	verif=1;
	while(IndicePunctPlecare !=IndicePunctCurent || verif){
		verif=0;
		a.push_back(IndicePunctCurent);
		pozitie=IndicePunctCurent;
		maxu=10000;
		for(i=1;i<=n;i++){
			if(viz[i]||i==IndicePunctCurent) continue;
			    unghi=atan2((x[i]-x[IndicePunctCurent]),(y[i]-y[IndicePunctCurent]));
			if(unghi<0)
				unghi+=2*M_PI;
			unghi-=u;
			if(unghi<0)
				unghi+=2*M_PI;
			if(maxu>unghi){
				maxu=unghi;
				pozitie=i;
			}
		}
		u=atan2(-(x[IndicePunctCurent]-x[pozitie]),-(y[IndicePunctCurent]-y[pozitie]));
		IndicePunctCurent=pozitie;
		if(u<0)
			u+=2*M_PI;
		viz[IndicePunctCurent]=1;
	}
	int dim=a.size();
	printf("%d\n",dim);
	for(i=0;i<dim;i++)
		printf("%lf %lf\n",x[a[i]],y[a[i]]);
	return 0;
}