Cod sursa(job #3359323)

Utilizator Palyo_Muset_AndreiPalyo-Muset Andrei Palyo_Muset_Andrei Data 27 iunie 2026 00:22:09
Problema Infasuratoare convexa Scor 50
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#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;
}