Pagini recente » Cod sursa (job #1460454) | Cod sursa (job #804899) | Cod sursa (job #2695408) | Cod sursa (job #1847795) | Cod sursa (job #2380423)
#include <bits/stdc++.h>
using namespace std;
const int nmax=120005;
struct numere{double x, y;};
numere v[nmax];
numere st[nmax];
numere dr[nmax];
numere oks[nmax];
numere okd[nmax];
int dir(numere a, numere b, numere c)
{
double s;
s=a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
if(s>0)
s=1;
if(s<0)
s=-1;
int sol=s;
return sol;
}
int cmp(numere a, numere b)
{
if(a.y<b.y)
return 1;
else if(a.y==b.y && a.x<b.x)
return 1;
return 0;
}
int infas(numere v[], numere ok[], int n, int semn)
{
int i=2,k=2;
ok[0]=v[0];
ok[1]=v[1];
while(i<n)
{
while(k>1 && dir(ok[k-2],ok[k-1],v[i])*semn>0)
k--;
ok[k]=v[i];
k++;
i++;
}
return k;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n,i,poz,k1,k2;
scanf("%d", &n);
for(i=0; i<n; i++)
scanf("%lf%lf", &v[i].x, &v[i].y);
sort(v,v+n,cmp);
k1=k2=1;
st[0]=v[0];
dr[0]=v[0];
for(i=1; i<n-1; i++)
if(dir(v[0],v[n-1],v[i])>0)
st[k1++]=v[i];
else
dr[k2++]=v[i];
st[k1++]=v[n-1];
dr[k2++]=v[n-1];
k1=infas(st,oks,k1,1);
k2=infas(dr,okd,k2,-1);
printf("%d\n",k1+k2-2);
for(i=0; i<k2-1; i++)
printf("%lf %lf\n",okd[i].x,okd[i].y);
for(i=k1-1; i>0; i--)
printf("%lf %lf\n",oks[i].x,oks[i].y);
return 0;
}