Cod sursa(job #3359144)

Utilizator gglvxxGlavan Andrei Gabriel gglvxx Data 25 iunie 2026 07:55:33
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <stdio.h>
#include <stdlib.h>

#define EPS 1e-9

typedef struct {
    double x, y;
} punct;

int compara(const void *a, const void *b) {
    punct *p1=(punct*)a;
    punct *p2=(punct*)b;
    if (p1->x!=p2->x) {
        return (p1->x>p2->x)-(p1->x<p2->x);
    }
    return (p1->y>p2->y)-(p1->y<p2->y);
}

double produs_vect(punct A, punct B, punct C) {
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

punct puncte[120005];
punct inf_conv[240010];

int main() {
    FILE *f=fopen("infasuratoare.in", "r");
    FILE *g=fopen("infasuratoare.out", "w");
    
    if (f==NULL || g==NULL) 
    {
        return 0;
    }

    int n;
    if (fscanf(f, "%d", &n)!=1) 
    {
        fclose(f);
        fclose(g);
        return 0;
    }
    for (int i=0; i<n; i++) {
        fscanf(f, "%lf %lf", &puncte[i].x, &puncte[i].y);
    }
    qsort(puncte, n, sizeof(punct), compara);
    int H=0;
    for (int i=0; i<n; i++) {
        while (H>=2 && produs_vect(inf_conv[H-2], inf_conv[H-1], puncte[i])<=EPS) {
            H--;
        }
        inf_conv[H++]=puncte[i];
    }

    int limita_jos=H;
    for (int i=n-2; i>=0; i--) {
        while (H>limita_jos && produs_vect(inf_conv[H-2], inf_conv[H-1], puncte[i])<=EPS) {
            H--;
        }
        inf_conv[H++]=puncte[i];
    }
    if (n>1) {
        H--;
    }
    fprintf(g, "%d\n", H);
    for (int i=0; i<H; i++) {
        fprintf(g, "%.6lf %.6lf\n", inf_conv[i].x, inf_conv[i].y);
    }
    fclose(f);
    fclose(g);
    return 0;
}