Pagini recente » Cod sursa (job #1120564) | Cod sursa (job #1768979) | Cod sursa (job #351746) | Cod sursa (job #1362674) | Cod sursa (job #371776)
Cod sursa(job #371776)
#include<fstream>
#include<iostream>
using namespace std;
double x[125000],y[125000];
long a[125000],sol[125000],cont,mi;
void qs(long i, long j)
{
long s=i,d=j,aux,piv=((i+j)>>1);
while(s<=d)
{
while((y[a[s]]-y[mi])*(x[a[piv]]-x[mi])<(y[a[piv]]-y[mi])*(x[a[s]]-x[mi]))s++;
while((y[a[d]]-y[mi])*(x[a[piv]]-x[mi])>(y[a[piv]]-y[mi])*(x[a[d]]-x[mi]))d--;
if(s<=d)
{
aux=a[s];
a[s]=a[d];
a[d]=aux;
d--;
s++;
}
}
if(i<d)qs(i,d);
if(s<j)qs(s,j);
}
int det(long i1, long i2, long i3)
{
if(x[i1]*y[i2]+x[i2]*y[i3]+x[i3]*y[i1]>y[i1]*x[i2]+y[i2]*x[i3]+y[i3]*x[i1]) return 1;
else return 0;
}
int main()
{
long n,i,j,gasit;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n>>x[1]>>y[1];
mi=1;
for(i=2;i<=n;i++)
{
f>>x[i]>>y[i];
if(x[i]<x[mi])mi=i;
else if(x[i]==x[mi])if(y[i]<y[mi])mi=i;
}
a[1]=mi;
for(i=2;i<mi;i++)a[i]=i;
a[mi]=1;
for(i=mi+1;i<=n;i++)a[i]=i;
qs(2,n);
sol[1]=a[1];
sol[2]=a[2];
i=1;j=3;
while(a[j])
{
gasit=0;
while(!gasit&&a[j])
{
if(det(sol[i],sol[i+1],a[j]))
{
sol[i+2]=a[j];
i++;
j++;
gasit=1;
}
else
{
sol[i+1]=a[j];
j++;
}
}
}
g<<i+1<<endl;
for(j=1;j<=i+1;j++)g<<x[sol[j]]<<' '<<y[sol[j]]<<'\n';
return 0;
}