Pagini recente » Cod sursa (job #2600603) | Cod sursa (job #846731) | Cod sursa (job #456660) | Cod sursa (job #2450185) | Cod sursa (job #846833)
Cod sursa(job #846833)
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
using namespace std;
#define inf 0xffffff
#define Max 120001
#define eps 1e-6
struct point { double x,y; }s[Max],st[Max],dr[Max];
int n,nst,ndr;
bool sort_type(point a,point b){ return a.x<b.x; }
double delta(point a,point b,point c)
{/*
1 a.x a.y
1 b.x b.y
1 c.x c.y
1 a.x a.y
1 b.x b.y*/
return b.x*c.y + c.x*a.y + a.x*b.y - a.y*b.x - b.y*c.x - c.y*a.x;
}
void st_envelope()
{
int n=2;
for(int i=3;i<=nst;i++)
{
while(n>=2 && delta(st[n-1],st[i],st[n]) + eps < 0)n--;
st[++n]=st[i];
}
nst=n;
}
void dr_envelope()
{
int n=2;
for(int i=3;i<=ndr;i++)
{
while(n>=2 && delta(dr[n-1],dr[i],dr[n]) - eps > 0)n--;
dr[++n]=dr[i];
}
ndr=n;
}
void envelope()
{
sort(s+1,s+n+1,sort_type);
//for(int i=1;i<=n;i++)printf("%lf %lf\n",s[i].x,s[i].y);
point p = s[1], u = s[n];
st[++nst]=dr[++ndr]=p;
for(int i=2;i<n;i++)
if(delta(p,u,s[i])-eps>0) st[++nst]=s[i]; else dr[++ndr]=s[i];
st[++nst]=dr[++ndr]=u;
st_envelope();
dr_envelope();
//for(int i=1;i<=ndr;i++)printf("%lf %lf\n",dr[i].x,dr[i].y);
printf("%d\n",nst+ndr-2);
for(int i=nst;i>0;i--)printf("%lf %lf\n",st[i].x,st[i].y);
for(int i=2;i<ndr;i++)printf("%lf %lf\n",dr[i].x,dr[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf %lf",&s[i].x,&s[i].y);
envelope();
return 0;
}