Pagini recente » Cod sursa (job #1480650) | Cod sursa (job #636794) | Cod sursa (job #2361158) | Cod sursa (job #2190420) | Cod sursa (job #257148)
Cod sursa(job #257148)
#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;
}