Cod sursa(job #2809833)

Utilizator CaptnBananaPetcu Tudor CaptnBanana Data 27 noiembrie 2021 18:10:20
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int N = 1.2e5 + 1;
int n, varf, stiva[N];
pair<double, double> p[N];
bool vis[N];

inline double produsIncrucisat(pair<double, double> A, pair<double, double> B, pair<double, double> C){
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x); // valoarea componentei pe axa z a lui AB X AC
}

int main(){
    f >> n;
    for(int i = 1; i <= n; i++)
        f >> p[i].x >> p[i].y;

    f.close();
    sort(p + 1, p + n + 1);
    stiva[1] = 1;
    stiva[2] = 2;
    varf = 2;
    vis[1] = vis[2] = 1;
    for(int i = 3, k = 1; i > 0; i += (k = (i == n ? -k : k))){ // mergem de la 1 la n (sub dreapta), apoi de la n la 0 (peste dreapta)
        if(vis[i])
            continue;

        while(varf >= 2 && produsIncrucisat(p[stiva[varf - 1]], p[stiva[varf]], p[i]) < 1e-12)
            vis[stiva[varf--]] = 0;

        stiva[++varf] = i;
        vis[i] = 1;
    }

    g << fixed << setprecision(9) << varf - 1 << '\n';
    for(int i = 1; i < varf; i++)
        g << p[stiva[i]].x << ' ' << p[stiva[i]].y << '\n';

    g.close();
}