Cod sursa(job #554047)

Utilizator paul992Cirstean Paul paul992 Data 14 martie 2011 15:48:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct punct
{double x,y;};
punct p[120001];
int n,st[120001],vf;

bool cmp(punct l,punct r)
{return (l.x-p[1].x)*(r.y-p[1].y)>(r.x-p[1].x)*(l.y-p[1].y);}

void read()
{
scanf("%d ",&n);
for(int i=1;i<=n;i++)
scanf("%lf %lf",&p[i].x,&p[i].y);
}


int primul()
{int prim=1;
for(int i=1;i<=n;i++)
	if(p[i].x<=p[prim].x)
		if(p[i].x<p[prim].x||p[i].y<p[prim].y)
			prim=i;
return prim;}

int directie(long p1, long p2, long p3)
{
	return (p[p2].x-p[p1].x)*(p[p3].y-p[p1].y) > (p[p3].x-p[p1].x)*(p[p2].y-p[p1].y);
}


void solve()
{int prim=primul();
swap(p[1],p[prim]);
sort(p+2,p+1+n,cmp);
st[++vf]=1;
st[++vf]=2;
for(int i=3;i<=n;i++)
	{if(directie(st[vf-1],st[vf],i))
		st[++vf]=i;
	else
		{while(!directie(st[vf-1],st[vf],i)&&vf>=1)
			vf--;
		st[++vf]=i;}
	}
}

void print()
{printf("%d\n",vf);
for(int i=1;i<=vf;i++)
	printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);}

int main()
{freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
solve();
print();


return 0;}