Pagini recente » Cod sursa (job #2057699) | Cod sursa (job #564124) | Cod sursa (job #2103978) | Cod sursa (job #521917) | Cod sursa (job #412482)
Cod sursa(job #412482)
#include <fstream.h>
#include <math.h>
struct pct{
double x,y,cos;}v[120001],s[120001],v1[120001],v2[120001];
long n,vf,k,k1,i,a;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double dist(double x1,double y1,double x2,double y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
double cosinus(pct p,pct p0)
{
return (p.x-p0.x)/(dist(p0.x,p0.y,p.x,p.y));
}
void cit()
{
long i,poz;
double minx=5000,miny=5000;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
//v[i].cos=cosinus(v[i]);//gresit se calc unghiul cu p0
if(v[i].y<miny)
{
minx=v[i].x;
miny=v[i].y;
poz=i;
}
if(fabs(v[i].y-miny)<0.000000000001&&v[i].x<minx)
{
minx=v[i].x;
miny=v[i].y;
poz=i;
}
}
vf++;
s[vf]=v[poz];
k=0;
for(i=1;i<=n;i++)
if(i!=poz)
{
k++;
v1[k]=v[i];
v1[k].cos=cosinus(v1[k],v[poz]);
}
fin.close();
}
void poz(long li,long ls,long &a)
{
long i1=0,j1=-1,i=li,j=ls,c1;
pct c;
while(i<=j)
{
if(v1[i].cos<v1[j].cos)
{
c=v1[i];
v1[i]=v1[j];
v1[j]=c;
c1=i1;
i1=-j1;
j1=-c1;
}
if(fabs(v1[i].cos-v1[j].cos)<0.000000000001)
{
if(v1[i].x<v1[j].x)
{
c=v1[i];
v1[i]=v1[j];
v1[j]=c;
c1=i1;
i1=-j1;
j1=-c1;
}
if(fabs(v1[i].x-v1[j].x)<0.000000000001)
{
if(v1[i].y>v1[j].y)
{
c=v1[i];
v1[i]=v1[j];
v1[j]=c;
c1=i1;
i1=-j1;
j1=-c1;
}
}
}
i+=i1;
j+=j1;
}
a=i;
}
void sort(long li,long ls)
{
if(li<=ls)
{
poz(li,ls,a);
sort(li,a-1);
sort(a+1,ls);
}
}
void elimin()
{
long i,j;
double aux;
k1=0;
for(i=1;i<=k;i++)
if(v1[i].cos!=15)
{
aux=v1[i].cos;
j=i+1;
while(fabs(aux-v1[j].cos)<0.000000000001)
{
v1[j-1].cos=15;
j++;
}
k1++;
v2[k1]=v1[j-1];
v1[j-1].cos=15;
}
}
double det(pct p1,pct p2,pct p3)
{
return((p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x));
}
void infas()
{
long i;
double d;
vf++;
s[vf]=v2[1];
vf++;
s[vf]=v2[2];
for(i=3;i<=k1;i++)
{
d=det(s[vf],s[vf-1],v2[i]);
while(d>0)
{
vf--;
d=det(s[vf],s[vf-1],v2[i]);
}
vf++;
s[vf]=v2[i];
}
}
int main()
{
cit();
sort(1,k);
elimin();
infas();
fout<<vf<<"\n";
for(i=1;i<=vf;i++)
fout<<s[i].x<<" "<<s[i].y<<"\n";
fout.close();
return 0;
}