Cod sursa(job #3221114)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 5 aprilie 2024 22:39:57
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

#define dd double
#define point complex<dd>
#define x real()
#define y imag()

const int N = 120009;

int dot_product(point a, point b){return (conj(a) * b).x;}
int cross_product(point a, point b){return (conj(a) * b).y;}

int n, sz;
point v[N], stk[N];

signed main()
{
    cin >> n;

    double a, b;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a >> b;
        v[i] = a + b * 1i;
    }


    int p = 1;
    for(int i = 2; i <= n; ++i)
        if(v[i].x < v[p].x || (v[i].x == v[p].x && v[i].y > v[p].y))
            p = i;

    swap(v[1], v[p]);


    sort(v + 2, v + n + 1, [&](point a, point b){return cross_product(a - v[1], b - v[1]) < 0;});

    stk[++sz] = v[1];
    for(int i = 2; i <= n; ++i)
    {
        while(sz >= 2 && cross_product(stk[sz] - stk[sz - 1], v[i] - stk[sz - 1]) > 0)sz --;
        stk[++ sz] = v[i];
    }

    cout << sz << '\n';
    cout << fixed << setprecision(6);
    for(int i = 1; i <= sz; ++i)cout << stk[i].x << ' ' << stk[i].y << '\n';
    return 0;
}