Cod sursa(job #2416528)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 27 aprilie 2019 17:53:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 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], start;

int ans[MAXN];

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 main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int n, poss = 0;
    fin >> n;
    start.x = start.y = 1e9;
    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];
            poss = i;
        }
    }
    swap(pct[1], pct[poss]);
    sort(pct + 2, pct + n + 1, comp);
    int len = 0;
    ans[++len] = 2;
    ans[++len] = 3;
    for(int i = 4; i <= n; ++i){
        punct ult = pct[ans[len]], pen = pct[ans[len - 1]];
        while(len > 1 && (ult.y - pen.y) * (pct[i].x - pen.x) > (pct[i].y - pen.y) * (ult.x - pen.x)){
            len--;
            if(len > 1){
                ult = pct[ans[len]];
                pen = pct[ans[len - 1]];
            }
        }
        ans[++len] = i;
    }
    ans[++len] = 1;
    fout << len << "\n";
    for(int i = 1; i <= len; ++i)
        fout << fixed << setprecision(6) << pct[ans[i]].x << " " << pct[ans[i]].y << "\n";
    return 0;
}