Cod sursa(job #685873)

Utilizator Robert29FMI Tilica Robert Robert29 Data 21 februarie 2012 11:28:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
int n,poz,nr,stv[120001];
double miny,minx;
struct pct
{
	double x,y,ctg;
}v[120001];
int cmp(pct a,pct b)
{
	return a.ctg>b.ctg;
}
int ver(double x1,double x2,double x3,double y1,double y2,double y3)
{
	double x=(x3-x2)*(y1-y2)-(x1-x2)*(y3-y2);
	if(x<0)
		return 1;
	return 0;
}
int main()
{
	fscanf(f,"%d",&n);
	miny=1000000000;
	for(int i=1;i<=n;++i)
	{
		fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
		if(miny>v[i].y)
		{
			miny=v[i].y;
			minx=v[i].x;
			poz=i;
		}
	}
	
	v[poz]=v[1];
	v[1].x=v[1].y=v[1].ctg=0;
	
	for(int i=2;i<=n;++i)
	{
		v[i].x-=minx;
		v[i].y-=miny;
		v[i].ctg=v[i].x/v[i].y;
	}
	
	sort(v+2,v+n+1,cmp);
	
	stv[1]=1;
	stv[2]=2;
	nr=2;
	
	for(int i=3;i<=n;++i)
	{
		while(nr>2&&ver(v[stv[nr-1]].x,v[stv[nr]].x,v[i].x,v[stv[nr-1]].y,v[stv[nr]].y,v[i].y))
			--nr;
		stv[++nr]=i;
	}
	
	fprintf(g,"%d\n",nr);
	for(int i=1;i<=nr;++i)
		fprintf(g,"%lf %lf\n",v[stv[i]].x+minx,v[stv[i]].y+miny);
	
	
	fclose(g);
	fclose(f);
	return 0;
}