Cod sursa(job #3214457)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 14 martie 2024 09:48:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 120010
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

pair<double, double> v[DIM], s[DIM], aux;
int n, k, i, p;

double det(const pair<double, double> &a, const pair<double, double> &b, const pair<double, double> &c) {
    return (b.first-a.first)*(c.second-a.second) - (c.first-a.first)*(b.second-a.second);
}

int cmp( const pair<double, double> &a, const pair<double, double> &b  ) {
    return det(v[1], a, b) > 0;
}
int main() {
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].first>>v[i].second;

    p = 1;
    for (i=2;i<=n;i++)
        if (v[i] < v[p])
            p = i;

    aux = v[1];
    v[1] = v[p];
    v[p] = aux;

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

    s[1] = v[1];
    s[2] = v[2];
    k = 2;

    for (i=3;i<=n;i++) {
        while (k >= 2 && det(s[k-1], s[k], v[i]) <= 0  ) {
            k--;
        }
        s[++k] = v[i];
    }

    fout<<k<<"\n";
    for (i=1;i<=k;i++)
        fout<<setprecision(9)<<fixed<<s[i].first<<" "<<s[i].second<<"\n";

    return 0;
}