Pagini recente » Cod sursa (job #2772536) | Cod sursa (job #2069132) | Cod sursa (job #2279339) | Cod sursa (job #2485234) | Cod sursa (job #288386)
Cod sursa(job #288386)
#include <fstream.h>
#include <math.h>
#include <iomanip.h>
double x[120000],y[120000],m[120000],pi=3.141592653589793238462643382785,min=0.000000000001;
long n,sol[120000],k,nr;
double unghi(double x,double y)
{
double sinus,cosinus;
if(y<min && x<min)
return 0;
sinus=double(y/sqrt(y*y+x*x));
cosinus=double(x/sqrt(y*y+x*x));
if(cosinus<min)
{
if(sinus>min)
return pi/2;
else
if(sinus<min)
return 3*pi/2;
}
else
{
if(sinus>min && cosinus>min)
return atan(sinus/cosinus);
if(sinus>min && cosinus<min)
return pi-atan(sinus/(-cosinus));
if(sinus<=min && cosinus>min)
{
if(atan((-sinus)/cosinus)<min)
return 0;
return 2*pi-atan((-sinus)/cosinus);
}
}
}
void cit()
{
long i;
ifstream fin("infasuratoare.in");
fin>>n;
for(i=1;i<=n;i++)
{
fin>>x[i]>>y[i];
m[i]=unghi(x[i],y[i]);
}
fin.close();
}
void minm()
{
long i,j=1;
double aux;
for(i=2;i<=n;i++)
if(y[i]<y[j] || (y[i]==y[j] && x[i]<x[j]))
j=i;
aux=x[j]; x[j]=x[1]; x[1]=aux;
aux=y[j]; y[j]=y[1]; y[1]=aux;
aux=m[j]; m[j]=m[1]; m[1]=aux;
}
void poz(long li,long ls)
{
long ii=0,jj=-1,i=li,j=ls,c;
double aux;
while(i<j)
{
if(m[i]>m[j] || (((y[i]-y[j]<min && y[i]-y[j]>=0) || (y[j]-y[i]<min && y[j]-y[i]>=0)) && y[i]>y[j]))
{
aux=x[i]; x[i]=x[j]; x[j]=aux;
aux=y[i]; y[i]=y[j]; y[j]=aux;
aux=m[i]; m[i]=m[j]; m[j]=aux;
c=ii;
ii=-jj;
jj=-c;
}
i+=ii;
j+=jj;
}
k=i;
}
void quick(long li,long ls)
{
if(li<ls)
{
poz(li,ls);
quick(li,k-1);
quick(k+1,ls);
}
}
int det(long p1,long p2,long p3)
{
double d;
//d=x[p1]*y[p2]+x[p2]*y[p3]+x[p3]*y[p1]-x[p3]*y[p2]-x[p2]*y[p1]-x[p1]*y[p3];
d=(x[p2]-x[p1])*(y[p3]-y[p1])-(x[p3]-x[p1])*(y[p2]-y[p1]);
if(d>=0)
return 0;
return 1;
}
void rez()
{
long i;
nr=3;
sol[1]=1; sol[2]=2;
for(i=3;i<=n;i++)
{
while(nr>=2 && det(sol[nr],i,sol[nr-1]))
nr--;
nr++;
sol[nr]=i;
}
while(nr>=3 && det(sol[nr-2],sol[nr-1],sol[nr]))
nr--;
}
void afis()
{
long i;
ofstream fout("infasuratoare.out");
fout<<nr<<'\n';
fout.precision(12);
for(i=1;i<=nr;i++)
fout<<setiosflags(ios::showpoint)<<x[sol[i]]<<" "<<y[sol[i]]<<'\n';
}
int main()
{
cit();
minm();
quick(2,n);
rez();
afis();
return 0;
}