Cod sursa(job #3359375)

Utilizator dragos_22Dragos-Radu Stiuca dragos_22 Data 27 iunie 2026 15:27:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

#define MAX_N 120005
#define x first
#define y second

typedef pair<double,double> Point;

int n;
int head;
Point v[MAX_N];
int st[MAX_N];

double crossProduct(Point O, Point A, Point B){
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x)*(A.y - O.y);
}

void convex_hull(){
    sort(v+1,v+n+1);

    head = 0;

    for(int i = 1;i <= n; ++i){
        while(head >= 2 && crossProduct(v[st[head-1]],v[st[head]],v[i]) <= 0)
            head--;
        st[++head] = i;
    }

    int sizeJos = head;
    for(int i = n-1;i >= 1; --i){
        while(head > sizeJos && crossProduct(v[st[head-1]],v[st[head]],v[i]) <= 0)
            head--;
        st[++head] = i;
    }

    cout << head - 1 << '\n';
    for(int i = 1;i < head; ++i)
        cout << v[st[i]].x << " " << v[st[i]].y << '\n';
}

int main(){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    cin >> n;
    cout << setprecision(6) << fixed;
    for(int i = 1;i <= n; ++i){
        cin >> v[i].x >> v[i].y;
    }

    convex_hull();
    return 0;
}