Cod sursa(job #3300580)

Utilizator fabiplavatPlavat Fabian-Remus fabiplavat Data 17 iunie 2025 14:38:30
Problema Infasuratoare convexa Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 120001

struct punct
{
    float x, y;
};

int n;
int varf=0;
int vis[MAX];
int stiva[MAX];

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

void read(struct punct *space,FILE* fin)
{
    for (int i = 0; i < n; i++)
    {
        fscanf(fin,"%f %f", &space[i].x, &space[i].y);
    }
}

double crossproduct(struct punct a, struct punct b, struct punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x -a.x);
}

void infasuratoare(struct punct *space, int n,FILE* fout)
{
    qsort(space, n, sizeof(struct punct), cmp);
    varf = 0;

    for (int i = 0; i < n; i++) {
        while (varf >= 2 && crossproduct(space[stiva[varf - 2]], space[stiva[varf - 1]], space[i]) <= 0) {
            vis[stiva[--varf]] = 0;
        }
        stiva[varf++] = i;
        vis[i] = 1;
    }

    int t = varf;
    for (int i = n - 2; i >= 0; i--) {
        if (vis[i]) continue;
        while (varf > t && crossproduct(space[stiva[varf - 2]], space[stiva[varf - 1]], space[i]) <= 0) {
            vis[stiva[--varf]] = 0;
        }
        stiva[varf++] = i;
        vis[i] = 1;
    }

    fprintf(fout,"%d\n", varf);
    for(int i=0;i<=varf-1;i++)
    {
        fprintf(fout,"%f %f\n", space[stiva[i]].x,space[stiva[i]].y);
    }


}

int main()
{
    FILE *fin,*fout;
    fin= fopen("infasuratoare.in", "r");
    fout= fopen("infasuratoare.out", "w");
    fscanf(fin,"%d", &n);
    struct punct space[n];
    read(space,fin);
    infasuratoare(space, n, fout);

}