Cod sursa(job #3359310)

Utilizator Olariu_MarioOlariu Mario Andrei Olariu_Mario Data 26 iunie 2026 19:47:59
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x,y;
}punct;

punct pivot;

double produs(punct o,punct a,punct b) 
{
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}

double dist_sq(punct p1, punct p2) 
{
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}

int compareunghi(const void *vp1, const void *vp2) 
{
    punct *p1=(punct *)vp1;
    punct *p2=(punct*)vp2;
    double cp=produs(pivot, *p1, *p2);
    if (cp>1e-12) 
        return -1;
    if (cp < -1e-12) 
        return 1;
    double d1=dist_sq(pivot, *p1);
    double d2=dist_sq(pivot, *p2);
    if (d1 < d2) 
        return -1;
    if (d1 > d2) 
        return 1;
    return 0;
}

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

    int n;
    fscanf(fin, "%d", &n);
    punct *pts=(punct*)malloc(n * sizeof(punct));
    for (int i=0;i<n;++i)
        fscanf(fin, "%lf %lf", &pts[i].x, &pts[i].y);
    int pivot_idx = 0;
    for (int i=1;i<n;i++) 
    {
        if (pts[i].y<pts[pivot_idx].y || (pts[i].y==pts[pivot_idx].y && pts[i].x<pts[pivot_idx].x)) 
            pivot_idx=i;
    }
    punct temp = pts[0];
    pts[0] = pts[pivot_idx];
    pts[pivot_idx] = temp;
    pivot = pts[0];
    qsort(&pts[1],n-1,sizeof(punct),compareunghi);
    punct *hull=(punct *)malloc(n*sizeof(punct));
    int top = 0;
    hull[top++]=pts[0];
    if (n > 1) 
        hull[top++]=pts[1];
    for (int i = 2; i < n; i++)
     {
        while (top>=2 && produs(hull[top-2],hull[top-1],pts[i])<=1e-12)
            top--;
        hull[top++]=pts[i];
    }
    fprintf(fout, "%d\n", top);
    for (int i = 0; i < top; i++)
        fprintf(fout,"%.6lf %.6lf\n",hull[i].x,hull[i].y);
    fclose(fin);
    fclose(fout);
    free(pts);
    free(hull);
    return 0;
}