Cod sursa(job #509595)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 11 decembrie 2010 14:23:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#define  nmax 100005 
#include <cmath>
#include <cstdio>
#include <complex>


using namespace std;

int i,n,mxp;
int sol[nmax],last,k,move,signe,stk[nmax],vf;
double mx,cosine[nmax],mxy=25000;


struct pct
{
	double x, y, cs;
}P[nmax];
	
double ccw(int p1,int p2,int p3)
{
    return (P[p2].x - P[p1].x)*(P[p3].y - P[p1].y) - (P[p2].y - P[p1].y)*(P[p3].x - P[p1].x);
}
	
double argume(int i)
{	
	double cosine;
	if(P[i].x >= P[1].x)
	{
		double d1=P[i].x-P[1].x;
		double d2=sqrt((P[i].x-P[1].x)*(P[i].x-P[1].x) + (P[i].y-P[1].y)*(P[i].y-P[1].y));
		cosine=d1/d2;
	}
	else
	{
		double d1=P[1].x-P[i].x;
		double d2=sqrt((P[i].x-P[1].x)*(P[i].x-P[1].x) + (P[i].y-P[1].y)*(P[i].y-P[1].y));
		cosine=d1/d2;
		cosine=cosine*(-1);
	}
	return cosine;
}

	
	
struct cmp
{
	bool operator()(const pct &a,const pct &b)
	{
		if(a.cs>b.cs)
			return 1;
		return 0;
	}
};


int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lf %lf",&P[i].x,&P[i].y);
	for(i=1;i<=n;i++)
	{
		if(P[i].x<mxy)
		{
			mxy=P[i].x;
			mxp=i;
		}
		else
			if(P[i].x==mxy)
			{
				if(P[i].y<P[mxp].y)
					mxp=i;
			}
	}
	
		
	for(i=2;i<=n;i++)
		P[i].cs=argume(i);
	
	swap(P[1],P[mxp]);
	sort(P+2,P+n+1,cmp());
	stk[1]=1;
	stk[2]=2;
	vf=2;
	for(i=3;i<=n;i++)
	{	
		
		while(ccw(stk[vf-1],stk[vf],i)<=0 && vf>=2)
			vf--;
		stk[++vf]=i;
	}
	
	printf("%d\n",vf);
	/*for(i=1;i<=n;i++)
		printf("%lf %lf\n",P[i].x, P[i].y);
	printf("\n");*/
	for(i=1;i<=vf;i++)
		printf("%lf %lf\n",P[stk[i]].x, P[stk[i]].y);
	
	return 0;
}