Cod sursa(job #913424)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 13 martie 2013 14:41:49
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point
{
	double x,y;
	bool u;
}v[120001];

int n,i,k,p,sol[120001],s[120001],t,j;
double eps=1e-12;

bool cmp (point A, point B)
{
	if (fabs(A.y-B.y)<=eps) return (A.x<B.x);
	return (A.y<B.y);
}

bool det (point A,point B,point C)
{
	return A.x*B.y+B.x*C.y+C.x*A.y-(C.x*B.y+B.x*A.y+A.x*C.y)>0;
}

int main ()
{
    fin>>n;
    for (i=1;i<=n;i++) fin>>v[i].x>>v[i].y;
    sort (v+1,v+n+1,cmp);
    k=0;p=1;
    for (i=1;i>0;i=i+p)
    {
    	if (v[i].u==1) continue;
    	s[++k]=i; v[i].u=1;
    	if (k<3) continue;
    	while (k>2&&det(v[s[k]],v[s[k-1]],v[s[k-2]]))
    	{
    		v[s[k-1]].u=0;
    		s[k-1]=s[k];
    		k--;
    	}
    	if (i==n) 
    	{
    		p=-1;
    		for (j=1;j<=k;j++) sol[j]=s[j];
    		t=k;
    		k=1;
    		s[k]=n;
    	}
    }
    for (i=2;i<=k;i++) sol[t-1+i]=s[i];
    t=t+k-1;
    fout<<t<<"\n";
    for (i=1;i<=t;i++) fout<<fixed<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
}