Cod sursa(job #3300813)

Utilizator pescarucristianPescaru Cristian Alexandru pescarucristian Data 19 iunie 2025 11:41:35
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define NMAX 120005

struct point{
    double x,y;
}a[NMAX],b[2 * NMAX];
int n,len;

int cmp(point a, point b){
    if(a.x < b.x){b
        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(const point& a, const point& b, const point& c){
    return (b.x - a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

void hull(){
    for(int i=0;i<n;++i){
        while(len >= 2 && cross(b[len-2], b[len-1],a[i])<=0)
            len--;
        b[len++]=a[i];
    }
    int lenU = len +1;
    for(int i=n-2; i>=0; --i){
        while(len >= lenU && cross(b[len-2],b[len-1],a[i])<=0)
            len--;
        b[len++] = a[i];
    }
    len--;
}

int main()
{
    f>>n;
    for(int i=0; i<n; ++i){
        f>>a[i].x>>a[i].y;
    }
    sort(a,a + n ,cmp);
    hull();
    g<<len<<'\n';
    for(int i=0; i<len; ++i){
        g<<b[i].x<<" "<<b[i].y<<'\n';
    }
    f.close();
    g.close();
    return 0;
}