Pagini recente » Cod sursa (job #2638905) | Cei mai harnici utilizatori infoarena | Cod sursa (job #3274602) | Cod sursa (job #2873662) | Cod sursa (job #884822)
Cod sursa(job #884822)
#include<cstdio>
#include<algorithm>
using namespace std;
int n,p,nr,k;
double cpx,cpy,pan;
struct coord
{
double x;
double y;
} v[120005];
struct panta
{
double m;
double mx;
double my;
} a[120005];
struct stiva
{
double xstv;
double ystv;
} stv[120005];
bool cmp(panta b,panta c)
{
return(b.m<c.m);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
cpx=cpy=1000000005;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if(v[i].x<cpx)
{
cpx=v[i].x;
cpy=v[i].y;
p=i;
}
else
if(v[i].x==cpx && v[i].y<cpy)
{
cpy=v[i].y;
p=i;
}
}
nr=0;
for(int i=1;i<=n;i++)
{
if(i!=p)
{
pan=(v[i].y-cpy)/(v[i].x-cpx);
a[++nr].m=pan;
a[nr].mx=v[i].x;
a[nr].my=v[i].y;
}
}
sort(a+1,a+n,cmp);
for(int i=1;i<n;i++)
{
while(k>=2 && ((stv[k].xstv-stv[k-1].xstv)*(a[i].my-stv[k-1].ystv)-(stv[k].ystv-stv[k-1].ystv)*(a[i].mx-stv[k-1].xstv)) <0 )
k--;
stv[++k].xstv=a[i].mx;
stv[k].ystv=a[i].my;
}
while(k>=2 && ((stv[k].xstv-stv[k-1].xstv)*(cpy-stv[k-1].ystv)-(stv[k].ystv-stv[k-1].ystv)*(cpx-stv[k-1].xstv)) <0 )
k--;
stv[++k].xstv=cpx;
stv[k].ystv=cpy;
printf("%d\n",k);
for(int i=1;i<=k;i++)
printf("%.6lf %.6lf\n",stv[i].xstv,stv[i].ystv);
return 0;
}