Pagini recente » Cod sursa (job #2778278) | Cod sursa (job #3359323)
#include <stdio.h>
#include <math.h>
#define precision 1e-12
#define PI 3.14159265358979323846
long double points[120001][2];
long double hull[120001][2];
long double dist(long double x1,long double y1,long double x2,long double y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
long double angle_diff(long double a,long double b)
{
long double diff=a-b;
while(diff<0)
diff+=2*PI;
while(diff>=2*PI)
diff-=2*PI;
return diff;
}
int main()
{
FILE *fr,*fw;
fr=fopen("infasuratoare.in","r");
if(!fr)
{
fprintf(stderr,"Failed to open read file");
return -1;
}
fw=fopen("infasuratoare.out","w");
if(!fw)
{
fprintf(stderr,"Failed to open write file");
fclose(fr);
return -1;
}
int N;
fscanf(fr,"%d",&N);
int start=0;
for(int i=0;i<N;i++)
{
fscanf(fr,"%Lf %Lf",&points[i][0],&points[i][1]);
if(points[i][0]<points[start][0])
start=i;
else if(points[i][0]==points[start][0] && points[i][1]<points[start][1])
start=i;
}
int current=start;
int H=0;
long double last_angle=-PI/2;
while(1)
{
hull[H][0]=points[current][0];
hull[H][1]=points[current][1];
H++;
int next=-1;
long double best_diff=10;
for(int i=0;i<N;i++)
{
if(i!=current)
{
long double angle=atan2l(points[i][1]-points[current][1],points[i][0]-points[current][0]);
long double diff=angle_diff(angle,last_angle);
if(next==-1 || diff<best_diff-precision)
{
best_diff=diff;
next=i;
}
else if(fabsl(diff-best_diff)<precision)
{
long double d1=dist(points[current][0],points[current][1],points[next][0],points[next][1]);
long double d2=dist(points[current][0],points[current][1],points[i][0],points[i][1]);
if(d2>d1)
next=i;
}
}
}
last_angle=atan2l(points[next][1]-points[current][1],points[next][0]-points[current][0]);
current=next;
if(current==start)
break;
}
fprintf(fw,"%d\n",H);
for(int i=0;i<H;i++)
fprintf(fw,"%.6Lf %.6Lf\n",hull[i][0],hull[i][1]);
fclose(fr);
fclose(fw);
return 0;
}