Pagini recente » Cod sursa (job #3236113) | Cod sursa (job #1666989) | Cod sursa (job #2964132) | Cod sursa (job #2824234) | Cod sursa (job #441761)
Cod sursa(job #441761)
#include <stdio.h>
#include <algorithm>
const char InFile[]="infasuratoare.in";
const char OutFile[]="infasuratoare.out";
const char RMode[]="r";
const char WMode[]="w";
const double EPS=1e-12;
const int MaxN=120005;
struct POINT
{
double x,y;
};
FILE *f;
POINT P[MaxN],H[MaxN];
long int N,HN;
int cmp_lf(double A, double B)
{
if(A+EPS<B)return -1;
if(B+EPS<A)return +1;
return 0;
}
bool cmp_POINT(POINT A,POINT B)
{
int c=cmp_lf(A.x,B.x);
if(c!=0)
{
return c==-1;
}
return cmp_lf(A.y,B.y)==-1;
}
int semn(POINT a,POINT b,POINT c)
{
double A=a.y-b.y, B=b.x-a.x, C=a.x*b.y-b.x*a.y;
return cmp_lf(A*c.x+B*c.y+C,0);
}
long int uz[MaxN],st[MaxN];
void ConvexHull()
{
std::sort(P+1,P+N+1,cmp_POINT);
int i=3,k=2,pas=1;
uz[2]=1;st[1]=1;st[2]=2;
while(!uz[1])
{
while(uz[i])
{
if(i==N)
{
pas=-1;
}
i+=pas;
}
while(k>=2 && semn(P[st[k-1]],P[st[k]],P[i])==-1)
{
uz[st[k--]]=0;
}
st[++k]=i;
uz[i]=1;
}
HN=k-1;
for(i=1;i<=HN;++i)
{
H[i]=P[st[i]];
}
}
int main()
{
f=fopen(InFile,RMode);
fscanf(f,"%ld",&N);
for(register int i=1;i<=N;++i)
{
fscanf(f,"%lf %lf",&P[i].x,&P[i].y);
}
fclose(f);
ConvexHull();
f=fopen(OutFile,WMode);
fprintf(f,"%ld\n",HN);
for(register int i=1;i<=HN;++i)
{
fprintf(f,"%.6lf %.6lf\n",H[i].x,H[i].y);
}
fclose(f);
return 0;
}