Cod sursa(job #2303677)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 16 decembrie 2018 18:48:59
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

#define punct pair<long double, long double>
#define x first
#define y second

const int MAXN = 120005;

punct pct[MAXN];
punct start;

bool comp(punct a, punct b){
    if(a.x == start.x || b.x == start.x){
        if(a.x == b.x)
            return a.y > b.y;
        return a.x > b.x;
    }
    double m1 = (start.y - a.y) / (start.x - a.x), m2 = (start.y - b.y) / (start.x - b.x);
    return m1 < m2;
}

int stk[MAXN];

int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int n;
    fin >> n;
    start.x = start.y = 1e9;
    int inds = 0;
    for(int i = 1; i <= n; ++i){
        fin >> pct[i].x >> pct[i].y;
        if(pct[i].x < start.x || (pct[i].x == start.x && pct[i].y < start.y)){
            start = pct[i];
            inds = i;
        }
    }
    swap(pct[1], pct[inds]);
    sort(pct + 2, pct + n + 1, comp);
    int vf = 0;
    stk[++vf] = 2;
    stk[++vf] = 3;
    for(int i = 4; i <= n; ++i){
        punct last = pct[stk[vf]], prec = pct[stk[vf - 1]];
        while(vf > 1 && (last.y - prec.y) * (pct[i].x - prec.x) > (pct[i].y - prec.y) * (last.x - prec.x)){
            vf--;
            if(vf > 1){
                last = pct[stk[vf]];
                prec = pct[stk[vf - 1]];
            }
        }
        stk[++vf] = i;
    }
    stk[++vf] = 1;
    fout << vf << "\n";
    for(int i = 1; i <= vf; ++i)
        fout << fixed << setprecision(7) << pct[stk[i]].x << " " << pct[stk[i]].y << "\n";
    return 0;
}