Cod sursa(job #407260)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 2 martie 2010 10:35:21
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define nn 120005
struct puncte{
	double x,y;	
};
puncte v[nn];
int z[nn],n,m;
double directie(int a,int b,int c)
{
	return ((v[b].x-v[a].x)*(v[c].y-v[a].y)-(v[b].y-v[a].y)*(v[c].x-v[a].x));
}
double functie(puncte a,puncte b)
{
	return (double)(a.x - v[1].x) * (b.y - v[1].y) > (double)(b.x - v[1].x) * (a.y - v[1].y);
}
void infasor(int pmin)
{
	//sort(v+2,v+n,functie);
	z[++m]=pmin;
	int gata=0;
	while(!gata)
	{
		for(int i=1;i<=n;++i)
		if(z[m]!=i)
		{
			int pp=1;
			for(int j=1;j<=n&&pp;++j)
				if(i!=j&&j!=z[m])
					if(directie(z[m],i,j)<0)
						pp=0;
			if(pp)
			{
				z[++m]=i;
				break;
			}
		}
		if(z[m]==z[1])gata=1;
	}
}
int main()
{
	ifstream fin("infasuratoare.in");
	fin>>n;
	for(int i=1;i<=n;++i)
		fin>>v[i].x>>v[i].y;
	int pmin=1;
	for(int i=2;i<=n;++i)
		if(v[i].y<v[pmin].y)
			pmin=i;
		else if(v[i].x==v[pmin].x)
				if(v[i].x<v[pmin].x)
					pmin=i;
	puncte aux=v[pmin];
	v[pmin]=v[1];
	v[1]=aux;
	infasor(pmin);
	FILE *f=fopen("infasuratoare.out","w");
	//ofstream fout("infasuratoare.out");
	fprintf(f,"%d\n",m-1);
	//fout<<m-1<<"\n";
	for(int i=1;i<m;++i)
		//fout<<v[z[i]].x<<" "<<v[z[i]].y<<"\n";
		fprintf(f,"%f %f\n",v[z[i]].x,v[z[i]].y);
	return 0;
}