Cod sursa(job #3300579)

Utilizator fabiplavatPlavat Fabian-Remus fabiplavat Data 17 iunie 2025 14:37:24
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_N 120005
#define EPS 1e-12

struct Point {
    double x, y;
};

int n;
struct Point v[MAX_N];
int st[MAX_N];
int head;
int vis[MAX_N];

int cmp(const void *a, const void *b) {
    struct Point *p = (struct Point *)a;
    struct Point *q = (struct Point *)b;
    if (fabs(p->x - q->x) > EPS) return (p->x < q->x) ? -1 : 1;
    if (fabs(p->y - q->y) > EPS) return (p->y < q->y) ? -1 : 1;
    return 0;
}

double cross_product(struct Point O, struct Point A, struct Point B) {
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

void read(FILE * fin) {
    fscanf(fin,"%d", &n);
    for (int i = 1; i <= n; ++i) {
        fscanf(fin,"%lf %lf", &v[i].x, &v[i].y);
    }
}

void convex_hull(FILE *fout) {
    qsort(v + 1, n, sizeof(struct Point), cmp);

    for (int i = 0; i <= n + 1; i++) vis[i] = 0;  

    st[1] = 1; st[2] = 2; head = 2;
    vis[2] = 1;

    for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p))) {
        if (vis[i]) continue;
        while (head >= 2 && cross_product(v[st[head - 1]], v[st[head]], v[i]) < EPS) {
            vis[st[head--]] = 0;
        }
        st[++head] = i;
        vis[i] = 1;
    }

    int hull_size = head - 1;
    fprintf(fout,"%d\n", hull_size);
    for (int i = 1; i < head; ++i) {
        fprintf(fout,"%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
    }
}

int main() {FILE *fin,*fout;
    fin= fopen("infasuratoare.in", "r");
    fout= fopen("infasuratoare.out", "w");
    read(fin);
    convex_hull(fout);
    return 0;
}