Cod sursa(job #3300839)

Utilizator pescarucristianPescaru Cristian Alexandru pescarucristian Data 19 iunie 2025 14:02:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 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;

bool cmp(const point& a, const point& b) {
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}

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 << fixed << setprecision(12);
    g<<len<<'\n';
    for(int i=0; i<len; ++i){
        g<<b[i].x<<" "<<b[i].y<<'\n';
    }
    f.close();
    g.close();
    return 0;
}