Pagini recente » Cod sursa (job #223745) | Cod sursa (job #1569875) | Cod sursa (job #1587864) | Cod sursa (job #1981736) | Cod sursa (job #309631)
Cod sursa(job #309631)
#include <stdio.h>
#include <math.h>
#include <cmath>
using namespace std;
#define dim 120005
#define lm 0.000000000001
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
typedef struct
{
double x,y,u1,u2;
} Punct;
long n,k;
Punct p[dim],s[dim];
void swap(Punct &p1,Punct &p2)
{
Punct px=p1;
p1=p2;
p2=px;
}
void read()
{
long i,j=1;
Punct pv;
fscanf(f,"%ld",&n);
for(i=1;i<=n;i++)
{
fscanf(f,"%lf %lf",&p[i].x,&p[i].y);
if(i==1||(p[i].y-pv.y<0)||(abs(p[i].y-pv.y)<=lm&&p[i].x-pv.x<0))
{
pv=p[i];
j=i;
}
}
swap(p[1],p[j]);
}
void assign()
{
long i;
for(i=2;i<=n;i++)
{
p[i].u1=p[i].x-p[1].x;
p[i].u2=p[i].y-p[1].y;
}
}
void qsort(long l,long r)
{
long i,j;
j=l-1;
for(i=l;i<=r;i++)
{
if(p[i].u2*p[r].u1<=p[r].u2*p[i].u1)
swap(p[i],p[++j]);
}
if(l<j-1)
qsort(l,j-1);
if(r>j+1)
qsort(j+1,r);
}
double clock(Punct p1,Punct p2,Punct p3)
{
return ((p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x));
}
void graham()
{
assign();
qsort(2,n);
s[++k]=p[n+1]=p[1];
long i;
for(i=2;i<=n;i++)
{
if(clock(s[k],p[i],p[i+1])<0)
s[++k]=p[i];
// else
// k--;
}
}
void show()
{
fprintf(g,"%ld\n",k);
long i;
for(i=1;i<=k;i++)
fprintf(g,"%.6lf %.6lf\n",s[i].x,s[i].y);
}
int main()
{
long i;
read();
graham();
show();
return 0;
}