Cod sursa(job #3359400)

Utilizator gratian-stefan.tothToth Gratian-Stefan gratian-stefan.toth Data 27 iunie 2026 18:50:19
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x, y;
} pct;

int comparePoints(const void* a,const void* b) {
    pct* p1=(pct*)a;
    pct* p2=(pct*)b;
    if (p1->x != p2->x) {
        return (p1->x < p2->x) ?-1:1;
    }
    if (p1->y != p2->y) {
        return (p1->y<p2->y) ?-1:1;
    }
    return 0;
}

double crossProduct(pct a,pct b,pct c) 
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

int main() 
{
    FILE *fin=fopen("infasuratoare.in","r");
    FILE *fout=fopen("infasuratoare.out","w");
    if (!fin || !fout) return 0;
    int n;
    if (fscanf(fin,"%d",&n)!=1) return 0;
    pct* points=(pct*)malloc(n*sizeof(pct));
    for (int i=0;i<n;++i) 
    {
        fscanf(fin,"%lf %lf",&points[i].x,&points[i].y);
    }
    qsort(points,n,sizeof(pct),comparePoints);
    pct* hull=(pct*)malloc(2*n*sizeof(pct));
    int h_size=0;

    for (int i=0;i<n;++i)
    {
        while (h_size>=2 && crossProduct(hull[h_size-2],hull[h_size-1],points[i])<=1e-11) 
        {
            h_size--;
        }
        hull[h_size++]=points[i];
    }
    int lower_size=h_size;
    for (int i=n-2;i>=0;--i) 
    {
        while (h_size>lower_size && crossProduct(hull[h_size-2],hull[h_size-1],points[i])<= 1e-11) 
        {
            h_size--;
        }
        hull[h_size++]=points[i];
    }
    if (h_size>1) h_size--;


    int start_idx = 0;
    for (int i=1;i<h_size;++i) 
        if (hull[i].y < hull[start_idx].y || (hull[i].y == hull[start_idx].y && hull[i].x < hull[start_idx].x))   start_idx = i;

    fprintf(fout,"%d\n",h_size);
    for (int i=0; i<h_size;++i) 
    {
        int idx=(start_idx+i) % h_size;
        fprintf(fout,"%.6f %.6f\n",hull[idx].x,hull[idx].y);
    }
    free(points);
    free(hull);
    fclose(fin);
    fclose(fout);

    return 0;
}