Pagini recente » Cod sursa (job #2525042) | Cod sursa (job #1230910) | Cod sursa (job #946214) | Cod sursa (job #1989207) | Cod sursa (job #372996)
Cod sursa(job #372996)
#include<fstream.h>
#include<iomanip.h>
#include<math.h>
double x[120100],y[120100],p[120100],xx[120100];
long a[120100],sol[120100],ssol[120100],mi;
long ls(long k)
{
return (k<<1);
}
long rs(long k)
{
return ((k<<1)+1);
}
long f(long k)
{
return (k>>1);
}
double dist(long i, long j)
{
double d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
return d;
}
void ex(long x, long y)
{
long aux;
aux=a[x];
a[x]=a[y];
a[y]=aux;
}
void sift(long n, long k)
{
long son;
do
{
son=0;
if(ls(k)<=n)
{
son=ls(k);
if(rs(k)<=n&&(p[a[rs(k)]]>p[a[son]]||p[a[rs(k)]]==p[a[son]]&&dist(a[rs(k)],mi)>dist(a[son],mi)))son=rs(k);
if(p[a[son]]<p[a[k]]||p[a[son]]==p[a[k]]&&dist(a[son],mi)<dist(a[k],mi))son=0;
}
if(son)
{
ex(k,son);
k=son;
}
}
while(son);
}
void bh(long n)
{
long i;
for(i=(n>>1);i;i--)sift(n,i);
}
void batman(long n)
{
long i;
bh(n);
for(i=n;i>1;i--)
{
ex(1,i);
sift(i-1,1);
}
}
int det(long q, long w, long e)
{
if(x[q]*y[w]+x[w]*y[e]+x[e]*y[q]>x[w]*y[q]+x[e]*y[w]+x[q]*y[e])return 2;
else
if(x[q]*y[w]+x[w]*y[e]+x[e]*y[q]==x[w]*y[q]+x[e]*y[w]+x[q]*y[e])return 1;
else return 0;
}
int main()
{
long max,k,n,j,i,t,b[120100],i1,i2;
double numa,numi,d,dmax,s,smax,l;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n>>x[1]>>y[1];
mi=1;
t=0;
for(i=2;i<=n;i++)
{
f>>x[i]>>y[i];
if(x[i]<x[mi]||x[i]==x[mi]&&y[i]<y[mi])mi=i;
}
k=0;
for(i=1;i<=n;i++)
if(x[mi]==x[i])b[++k]=i;
else
{
p[i]=(y[i]-y[mi])/(x[i]-x[mi]);
a[++t]=i;
}
max=b[1];
for(i=2;i<=k;i++)
if(y[b[i]]>y[max])max=b[i];
batman(t);
ssol[1]=mi;
ssol[2]=a[1];
i=2;j=2;
while(j<=t)
{
while(!det(ssol[i-1],ssol[i],a[j]))
i--;
ssol[++i]=a[j++];
}
if(k>1&&max!=mi)
ssol[++i]=max;
while(!det(ssol[i-2],ssol[i-1],ssol[i]))
{
ssol[i-1]=ssol[i];
i--;
}
sol[1]=ssol[1];
sol[2]=ssol[2];
k=2;
for(j=3;j<=i;j++)
{
if(det(sol[k-1],sol[k],ssol[j])==1)sol[k]=ssol[j];
else sol[++k]=ssol[j];
}
i=k;
g<<i<<'\n';
for(j=1;j<=i;j++)g<<fixed<<setprecision(6)<<x[sol[j]]<<' '<<y[sol[j]]<<'\n';
return 0;
}