Cod sursa(job #728865)

Utilizator paulbotabota paul paulbota Data 29 martie 2012 01:40:51
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<fstream>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define maxn 120010
#define pb push_back
#define mp make_pair
#define pi 3.1415

using namespace std;

ifstream in("infasuratoare.in");


vector<pair<double,double> > vec;
vector<int> rasp;
int N;

void read()
{
	in>>N;
	for(int i=1;i<=N;i++)
	{
		double x,y;
		in>>x>>y;
		vec.pb(mp(x,y));
	}
}

int main()
{
	int i,origine=0;
	read();
	for(i=0;i<(int)vec.size();i++)
	{
		if(vec[i].second<vec[origine].second) origine=i;
		else
		if(vec[i].second==vec[origine].second)
			if(vec[i].first<vec[origine].first)
				origine=i;
	}
	int poz=origine;
	bool prima=true,parc[maxn];
	double rest=0;
	for(i=0;i<=N;i++)
		parc[i]=false;
	while(prima == true || poz!=origine)
	{
		prima=false;
		double minim=1<<30;
		int posib=poz;
		rasp.pb(poz);
		for(i=0;i<N;i++)
		{
			if(parc[i]==true || i==poz) continue;
			double unghi=atan2((vec[i].second-vec[poz].second),(vec[i].first-vec[poz].first));
			if(unghi<0) unghi+=2*pi;
			unghi-=rest;
			if(unghi<0) unghi+=2*pi;
			if(unghi<minim)
			{
				minim=unghi;
				posib=i;
			}
		}
		rest=atan2((vec[posib].first-vec[poz].first),(vec[posib].second-vec[poz].second));
		if(rest<0) rest+=2*pi;
		poz=posib;
		parc[poz]=true;
	}
	freopen("infasuratoare.out","w",stdout);
	printf("%d\n",(int)rasp.size());
	for(i=0;i<(int)rasp.size();i++)
		printf("%lf %lf\n",vec[rasp[i]].first,vec[rasp[i]].second);
	return 0;
}