Cod sursa(job #3301136)

Utilizator robertcd29Chira Robert-Denis robertcd29 Data 21 iunie 2025 21:07:43
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
#include <stdlib.h>
typedef struct { double x, y; } P;
int cmp(const void *a, const void *b){
    P *p=(P*)a, *q=(P*)b;
    if(p->x<q->x) return -1;
    if(p->x>q->x) return 1;
    if(p->y<q->y) return -1;
    if(p->y>q->y) return 1;
    return 0;
}
double cross(P a, P b, P c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main(){
    int n;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    if(scanf("%d",&n)!=1) return 0;
    P *a = malloc(n*sizeof(P));
    for(int i=0;i<n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
    qsort(a,n,sizeof(P),cmp);
    P *h = malloc(2*n*sizeof(P));
    int m=0;
    for(int i=0;i<n;i++){
        while(m>=2 && cross(h[m-2],h[m-1],a[i])<=0) m--;
        h[m++]=a[i];
    }
    int t = m;
    for(int i=n-2;i>=0;i--){
        while(m>t && cross(h[m-2],h[m-1],a[i])<=0) m--;
        h[m++]=a[i];
    }
    if(m>1) m--;
    int start = 0;
    for(int i=1;i<m;i++){
        if(h[i].y < h[start].y || (h[i].y==h[start].y && h[i].x < h[start].x))
            start = i;
    }
    printf("%d\n",m);
    for(int i=0;i<m;i++){
        int idx = (start+i)%m;
        printf("%.6f %.6f\n", h[idx].x, h[idx].y);
    }
    return 0;
}