Cod sursa(job #3198063)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 28 ianuarie 2024 12:07:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <algorithm>

using namespace std;

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

const int N_MAX = 120001;
int n, p, py = INT_MAX, l;
int v[N_MAX], r[N_MAX];
double x[N_MAX], y[N_MAX];

bool cmp(const int& p1, const int& p2){
    return ((y[p1] - y[p]) * (x[p2] - x[p])) > ((y[p2] - y[p]) * (x[p1] - x[p]));
}

inline double semn(int p1, int p2, int p3){ /// formula la determinant
    return (x[p2] - x[p1]) * (y[p3] - y[p1]) - (x[p3] - x[p1]) * (y[p2] - y[p1]);
}

int main()
{
    f >> n;

    for(int i = 1; i <= n; ++i){
        v[i] = i;
        f >> x[i] >> y[i];
        if(py > y[i]){
            p = i;
            py = y[i];
        }
    }

    swap(v[p], v[1]); /// pun p pe primul loc

    sort(v + 2, v + n + 1, cmp);

    r[++l] = p, r[++l] = v[2];

    for(int i = 3; i <= n; ++i){
        while(semn(r[l-1], r[l], v[i]) > 0)
            l--;
        r[++l] = v[i];
    }

    g << l << '\n';

    for(int i = l; i > 0; --i)
        g << fixed << setprecision(12) << x[r[i]] << ' ' << setprecision(12) << y[r[i]] << '\n';

    return 0;
}