Cod sursa(job #2576774)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 6 martie 2020 22:33:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <bitset>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int maxn = 120005;
pair <double, double> v[maxn];
bitset <maxn> pus;
int stk[maxn];

inline bool det(double x1, double y1, double x2, double y2, double x3, double y3)
{
    if((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) < 0)
        return 0;
    return 1;
}

int main()
{
    int n;
    in >> n;
    for(int i = 1; i <= n; i++)
        in >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1);
    int poz = 0;
    stk[++poz] = 1;
    pus[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        pair <double, double> x = v[stk[poz - 1]];
        pair <double, double> y = v[stk[poz]];
        while(poz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
        {
            pus[stk[poz]] = 0;
            poz--;
            x = v[stk[poz - 1]];
            y = v[stk[poz]];
        }
        stk[++poz] = i;
        pus[i] = 1;
    }
    for(int i = n - 1; i >= 1; i--)
    {
        pair <double, double> x = v[stk[poz - 1]];
        pair <double, double> y = v[stk[poz]];
        if(!pus[i])
        {
            while(poz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
            {
                pus[stk[poz]] = 0;
                poz--;
                x = v[stk[poz - 1]];;
                y = v[stk[poz]];
            }
            stk[++poz] = i;
            pus[i] = 1;
        }
    }
    pair <int, int> x = v[stk[poz - 1]];
    pair <int, int> y = v[stk[poz]];
    while(poz >= 2 && !det(x.first, x.second, y.first, y.second, v[1].first, v[1].second))
    {
        pus[stk[poz]] = 0;
        poz--;
        x = v[stk[poz - 1]];;
        y = v[stk[poz]];
    }
    out << poz << "\n";
    for(int i = 1; i <= poz; i++)
        out << setprecision(6) << fixed << v[stk[i]].first << " " << setprecision(6) << fixed << v[stk[i]].second << "\n";
    return 0;
}