Cod sursa(job #3359324)

Utilizator Palyo_Muset_AndreiPalyo-Muset Andrei Palyo_Muset_Andrei Data 27 iunie 2026 00:38:38
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.58 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define precision 1e-12
#define MAXN 120005

long double points[MAXN][2];
long double hull[MAXN][2];

long double startx, starty;

long double cross(long double ax, long double ay, long double bx, long double by, long double cx, long double cy) 
{
    return (bx-ax)*(cy-ay)-(by-ay)*(cx-ax);
}

long double dist(long double x1, long double y1, long double x2, long double y2)
 {
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

int cmp(const void *a, const void *b) 
{
    long double *p1 = (long double*)a;
    long double *p2 = (long double*)b;

    long double value = cross(startx, starty, p1[0], p1[1], p2[0], p2[1]);

    if(value< -precision)
        return -1;

    if(value>precision)
        return 1;

    long double d1 = dist(startx, starty, p1[0], p1[1]);
    long double d2 = dist(startx, starty, p2[0], p2[1]);

    if(d1<d2)
        return -1;

    if(d1>d2)
        return 1;

    return 0;
}

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 = 1;

    for(int i = 1;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;
    }

    long double aux;

    aux = points[1][0];
    points[1][0] = points[start][0];
    points[start][0] = aux;

    aux = points[1][1];
    points[1][1] = points[start][1];
    points[start][1] = aux;

    startx = points[1][0];
    starty = points[1][1];

    qsort(points+2, N-1, sizeof(points[0]), cmp);

    hull[1][0] = points[1][0];
    hull[1][1] = points[1][1];

    hull[2][0] = points[2][0];
    hull[2][1] = points[2][1];

    int H = 2;

    for(int i = 3;i<= N;i++) 
    {
        while(H>= 2 && cross(hull[H-1][0], hull[H-1][1],hull[H][0], hull[H][1],points[i][0], points[i][1])>precision)
            H--;

        H++;
        hull[H][0] = points[i][0];
        hull[H][1] = points[i][1];
    }

    fprintf(fw, "%d\n", H);

    for(int i = H;i>= 1;i--)
        fprintf(fw, "%.9Lf %.9Lf\n", hull[i][0], hull[i][1]);

    fclose(fr);
    fclose(fw);

    return 0;
}