Cod sursa(job #408049)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 2 martie 2010 20:17:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define nn 120005
struct puncte{
	double x,y;	
};
puncte v[nn],z[nn];
int n,m;
double directie(puncte a,puncte b,puncte c)
{
	return ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
}
int polare(puncte A,puncte B)
{
    if(directie(v[1],A,B)>0)
      return 1;
    if(directie(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);
}

void infasor()
{
	sort(v+2,v+n,polare);
	m=0;
	z[++m]=v[1];
	z[++m]=v[2];
	int gata=0;
	for(int i=3;i<=n;++i)
    {
		while(directie(z[m-1],z[m],v[i])<=0 && m>1)
        --m;
		z[++m]=v[i];
    }
}
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();
	FILE *f=fopen("infasuratoare.out","w");
	//ofstream fout("infasuratoare.out");
	fprintf(f,"%d\n",m);
	//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",z[i].x,z[i].y);
	return 0;
}