Pagini recente » Cod sursa (job #558560) | Cod sursa (job #2301205) | Cod sursa (job #3140088) | Cod sursa (job #2569981) | Cod sursa (job #922067)
Cod sursa(job #922067)
#include<stdio.h>
#include<algorithm>
#define MAXN 120000
#define err 0.000000000001
using namespace std;
struct punct
{
double x,y;
}v[MAXN+1];
int st[MAXN+1],u,viz[MAXN+1],n;
void citire()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf %lf",&v[i].x,&v[i].y);
}
}
int cmp(punct a,punct b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
double produs(punct A,punct B,punct C)
{
return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
void infasura()
{
st[1]=1;
st[2]=2;
viz[2]=1;
viz[1]=1;
u=2;
for(int i=3;i<=n;i++)
{
while(u>=2 && produs(v[st[u-1]],v[st[u]],v[i])<err)
{
viz[st[u]]=0;
u--;
}
st[++u]=i;
viz[i]=1;
}
for(int i=n;i>0;i--)
{
if(viz[i])
continue;
while(u>=2 && produs(v[st[u-1]],v[st[u]],v[i])<err)
{
viz[st[u]]=0;
u--;
}
st[++u]=i;
viz[i]=1;
}
while(produs(v[st[u]],v[st[1]],v[st[2]])<err || produs(v[st[u-1]],v[st[u]],v[st[1]])<err)
u--;
}
void afisare()
{
freopen("infasuratoare.out","w",stdout);
printf("%d",u);
for(int i=1;i<=u;i++)
printf("\n%.6lf %.6lf",v[st[i]].x, v[st[i]].y);
}
int main()
{
citire();
sort(v+1,v+n+1,cmp);
infasura();
afisare();
return 0;
}