Cod sursa(job #3359383)

Utilizator alexandru.simoneaSimonea Alexandru alexandru.simonea Data 27 iunie 2026 16:28:49
Problema Infasuratoare convexa Scor 20
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 120005

typedef struct {
     double x, y; 
}Point;

Point pts[MAXN];
Point hull[MAXN];
int n, k;

int compare(const void *a, const void *b) 
{
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;

    if (p1->x < p2->x) 
        return -1;
    if (p1->x > p2->x) 
        return 1;
    if (p1->y < p2->y) 
        return -1;
    if (p1->y > p2->y) 
        return 1;
    
    return 0;
}

double cross(Point O, Point A, Point B) 
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
int main(void) 
{
    FILE *fin = fopen("infasuratoare.in", "r");
    FILE *fout = fopen("infasuratoare.out", "w");

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

    for (int i = 0; i < n; i++) 
        fscanf(fin, "%lf %lf", &pts[i].x, &pts[i].y);
    
    qsort(pts, n, sizeof(Point), compare);

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

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

    k--;
    fprintf(fout, "%d\n", k);
    for (int i = 0; i < k; i++) 
        fprintf(fout, "%.0lf %.0lf\n", hull[i].x, hull[i].y);

    fclose(fin);
    fclose(fout);

    return 0;
}