Cod sursa(job #406696)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 1 martie 2010 19:02:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
struct coord
{
	double x,y;
};
#define nn 120005
coord v[nn];
int z[nn],n,m;
int dir(coord A,coord B,coord C)
{
    double det=A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y;
    if(det==0)
      return 0;
    if(det<0)
      return -1;
    return 1;
}
int polare(coord A,coord B)
{
    if(dir(v[1],A,B)>0)
      return 1;
    if(dir(v[1],A,B)<0)
      return 0;
    return(v[1].x-A.x)*(v[1].x-A.x)+(v[1].y-A.y)*(v[1].y-A.y) <
          (v[1].x-B.x)*(v[1].x-B.x)+(v[1].y-B.y)*(v[1].y-B.y);
}
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);
}
int main()
{
	ifstream fin("infasuratorare.in");
	fin>>n;
	for(int i=1;i<=n;++i)
		fin>>v[i].x>>v[i].y;
	int p=1;	
	for(int i=2;i<=n;++i)
		if(v[p].x<v[i].x)
			p=i;
		else if(v[p].x==v[i].x)
			if(v[p].y<v[i].y)
				p=i;
	z[++m]=p;
	coord aux=v[1];
    v[1]=v[p];
    v[p]=aux;
	cout<<z[1];cin.get();
	//sort(v+2,v+n,polare);
	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;
	}
	FILE *f=fopen("infasuratoare.out","w");
	fprintf(f,"%d\n",m);
	for(int i=1;i<m;++i)
		fprintf(f,"%f %f\n",v[z[i]].x,v[z[i]].y);
	return 0;
}