Pagini recente » Cod sursa (job #1928365) | Profil BlackNesta | Cod sursa (job #2194676) | Cod sursa (job #1553608) | Cod sursa (job #460862)
Cod sursa(job #460862)
#include<cstdio>
#include<algorithm>
#define eps 1e-12
using namespace std;
struct ceva
{
double x,y;
};
ceva v[120005];
double supx[120005],supy[120005],infx[120005],infy[120005],aux;
double rap,raport;
int n,i,j,ka_s,ka_i,p,cont_sup,cont_inf;
int compar (double a,double b)
{
if (a+eps<b) return -1;
if (b+eps<a) return 1;
return 0;
}
int cmp (const ceva& a,const ceva& b)
{
if(!compar(a.x,b.x))
return (compar(a.y,b.y)==-1);
return (compar(a.x,b.x)==-1);
}
int main ()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
rap=(v[n].y-v[1].y)/(v[n].x-v[1].x);
ka_s=1; ka_i=1;
supx[1]=v[1].x;
supy[1]=v[1].y;
infx[1]=v[1].x;
infy[1]=v[1].y;
for (i=2; i<n; i++)
{
if (v[i].x-v[1].x==0) raport=rap+1;
else raport=(v[i].y-v[1].y)/(v[i].x-v[1].x);
if (raport>=rap) { ka_s++; supx[ka_s]=v[i].x; supy[ka_s]=v[i].y; }
else { ka_i++; infx[ka_i]=v[i].x; infy[ka_i]=v[i].y; }
}
ka_s++; ka_i++;
supx[ka_s]=v[n].x;
supy[ka_s]=v[n].y;
infx[ka_i]=v[n].x;
infy[ka_i]=v[n].y;
p=1; cont_sup=ka_s;
cont_inf=ka_i;
for (i=2; i<ka_s; i++)
if ((supy[i]-supy[p])/(supx[i]-supx[p])>=(supy[i+1]-supy[p])/(supx[i+1]-supx[p])) p++;
else { supx[i]=1000000002; cont_sup--; }
p=1;
for (i=2; i<ka_i; i++)
if ((infy[i]-infy[p])/(infx[i]-infx[p])<=(infy[i+1]-infy[p])/(infx[i+1]-infx[p])) p++;
else { infx[i]=1000000002; cont_inf--; }
printf("%d\n",cont_sup-1+cont_inf-1);
for (i=2; i<=ka_i; i++)
if (infx[i]!=1000000002) printf("%lf %lf\n",infx[i],infy[i]);
for (i=ka_s-1; i>=1; i--)
if (supx[i]!=1000000002) printf("%lf %lf\n",supx[i],supy[i]);
return 0;
}