Cod sursa(job #257148)

Utilizator IeewIordache Bogdan Ieew Data 12 februarie 2009 20:47:39
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream.h>
#include <stdlib.h>
#define InFile "infasuratoare.in"
#define OutFile "infasuratoare.out"
struct pct
{
double x,y;
}a[120001];
int n,v[120001],st[120001],k;

int sortf(const void*a, const void*b)
{
	return ((pct*)a)->y>((pct*)b)->y||((pct*)a)->y==((pct*)b)->y&&((pct*)a)->x>((pct*)b)->x;
}

int intladr(pct u,pct d,pct t)
{return (u.x*d.y+d.x*t.y+t.x*u.y-d.y*t.x-t.y*u.x-u.y*d.x)>=0;}

int main()
{int i;
ifstream in(InFile);
in>>n;
for(i=1;i<=n;i++)in>>a[i].x>>a[i].y;
in.close();
qsort(a+1,n,sizeof(a[0]),sortf);
//for(i=1;i<=n;i++)cout<<a[i].y<<' '<<a[i].x<<'\n';
v[1]=v[2]=1;
st[1]=1;st[2]=2;k=2;
for(i=3;i<=n;i++)
if(!v[i])
	if(k>1&&intladr(a[st[k-1]],a[st[k]],a[i]))
		{
		 v[st[k]]=0;
		 st[k]=0;
		 k--;
		 i--;		
		}
		else 
		{
			st[++k]=i;
			v[i]=1;
		}

for(i=n;i>0;i--)
	if(!v[i])
		if(k>1&&intladr(a[st[k-1]],a[st[k]],a[i]))
		{
		 v[st[k]]=0;
		 st[k]=0;
		 k--;
		 i++;
		}
		else
		{
			st[++k]=i;
			v[i]=1;
		} 
ofstream out(OutFile);
out<<k<<'\n'<<a[st[1]].x<<' '<<a[st[1]].y<<'\n';
for(i=k;i>=2;i--)out<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
out.close();		
return 0;
}