Pagini recente » Cod sursa (job #1638702) | Cod sursa (job #2365642) | Cod sursa (job #1182959) | Cod sursa (job #2488729) | Cod sursa (job #410260)
Cod sursa(job #410260)
#include <fstream.h>
#include <math.h>
struct pct{
double x,y,cos;}v[120001],s[120001],v1[120001],v2[120001];
int n,vf,k,k1,i,a;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
float dist(double x1,double y1,double x2,double y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
float cosinus(pct p,pct p0)
{
return (p.x-p0.x)/(dist(p0.x,p0.y,p.x,p.y));
}
void cit()
{
int 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.0001&&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(int li,int ls,int &a)
{
int 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;
}
i+=i1;
j+=j1;
}
a=i;
}
void sort(int li,int ls)
{
if(li<=ls)
{
poz(li,ls,a);
sort(li,a-1);
sort(a+1,ls);
}
}
void elimin()
{
int i,j;
k1=0;
for(i=1;i<=k;i++)
if(v1[i].cos!=101)
{
k1++;
v2[k1]=v1[i];
for(j=i+1;j<=k;j++)
if(fabs(v1[i].cos-v1[j].cos)<0.0001)
v1[j].cos=101;
else
break;
}
}
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()
{
int 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;
}