Pagini recente » Cod sursa (job #2069994) | Cod sursa (job #2726067) | Cod sursa (job #487522) | Cod sursa (job #460803) | Cod sursa (job #372083)
Cod sursa(job #372083)
#include<fstream.h>
#include<iomanip.h>
double x[125000],y[125000],p[125000];
long a[125000],sol[125000];
void batman(long i, long j)
{
long s=i,d=j,piv=((i+j)>>1),aux;
while(s<=d)
{
while(p[a[s]]<p[a[piv]])s++;
while(p[a[d]]>p[a[piv]])d--;
if(s<=d)
{
aux=a[s];a[s]=a[d];a[d]=aux;
s++;
d--;
}
if(i<d)batman(i,d);
if(s<j)batman(s,j);
}
}
int det(int q, int w, int 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 1;
else return 0;
}
int main()
{
long min, max=0,k,n,j,i;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n>>x[1]>>y[1];
min=1;
for(i=2;i<=n;i++)
{
f>>x[i]>>y[i];
if(x[i]<x[min]||x[i]==x[min]&&y[i]<y[min])min=i;
}
k=0;
for(i=1;i<min;i++)
if(x[i]==x[min])
max=i;
else
{
p[i]=(y[i]-y[min])/(x[i]-x[min]);
a[++k]=i;
}
for(i=min+1;i<=n;i++)
if(x[i]==x[min])
max=i;
else
{
p[i]=(y[i]-y[min])/(x[i]-x[min]);
a[++k]=i;
}
batman(1,k);
sol[1]=min;
sol[2]=a[1];
i=2;j=2;
while(j<=k)
{
while(!det(sol[i-1],sol[i],a[j]))i--;
sol[++i]=a[j++];
}
if(max)
sol[++i]=max;
g<<i<<'\n';
j=i;
for(i=1;i<=j;i++)
g<<fixed<<setprecision(6)<<x[sol[i]]<<' '<<y[sol[i]]<<'\n';
return 0;
}