Pagini recente » Cod sursa (job #726152) | Cod sursa (job #1145442) | Cod sursa (job #731655) | Cod sursa (job #197223) | Cod sursa (job #393642)
Cod sursa(job #393642)
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define Nmax 120010
struct pct
{
double x,y;
} v[Nmax];
int n,m;
int st[Nmax],vf;
double xi,yi;
void swap(int,int);
bool cmp(pct i,pct j)
{
return ( atan2(i.y - yi,i.x - xi) < atan2(j.y - yi,j.x - xi) );
}
double det(int i,int j,int k)
{
return ( v[i].x*v[j].y + v[j].x*v[k].y + v[k].x*v[i].y - v[k].x*v[j].y - v[j].x*v[i].y - v[i].x*v[k].y);
}
void solve()
{
st[++vf]=1;
v[++n]=v[1];
for(int i=2;i<=n;++i)
{
st[++vf]=i;
while (vf>2 && det(st[vf-2],st[vf-1],st[vf]) < 0 )
st[--vf]=i;
}
printf("%d\n",--vf);
for(int i=1;i<=vf;++i)
printf("%lf %lf\n",v[ st[i] ].x,v[ st[i] ].y);
}
int main()
{
m=1;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if (v[m].x > v[i].x)
m=i;
else
if (v[m].x == v[i].x && v[m].y > v[i].y)
m=i;
}
xi=v[m].x;
yi=v[m].y;
swap(m,1);
sort(v+2,v+n+1,cmp);
solve();
return 0;
}
void swap(int i,int j)
{
pct aux=v[i];
v[i]=v[j];
v[j]=aux;
}