Cod sursa(job #3359443)

Utilizator albu-sebastianAlbu Sebastian albu-sebastian Data 27 iunie 2026 21:39:58
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    double x, y;
} point;

point p[120005];
point h[240005];

int cmp(const void *a, const void *b)
{
    point *A = (point*)a;
    point *B = (point*)b;

    if (A->x < B->x) return -1;
    if (A->x > B->x) return 1;

    if (A->y < B->y) return -1;
    if (A->y > B->y) return 1;

    return 0;
}

double cross(point A, point B, point 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");

    int n;
    fscanf(fin, "%d", &n);

    for(int i=0;i<n;i++)
    {
        fscanf(fin,"%lf%lf",&p[i].x,&p[i].y);
    }
    qsort(p,n,sizeof(point),cmp);

    int k=0;

    for(int i=0;i<n;i++)
    {
        while(k>=2 && cross(h[k-2],h[k-1],p[i])<=0)
        {
            k--;
        }
        h[k++]=p[i];
    }

    int t = k+1;

    for(int i=n-2;i>=0;i--)
    {
        while(k>=t && cross(h[k-2],h[k-1],p[i])<=0)
            k--;

        h[k++]=p[i];
    }

    k--;

    fprintf(fout,"%d\n",k);

    for(int i=0;i<k;i++)
    {
        fprintf(fout,"%.12lf %.12lf\n",h[i].x,h[i].y);
    }
    fclose(fin);
    fclose(fout);

    return 0;
}