Cod sursa(job #1820222)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 1 decembrie 2016 13:34:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <bitset>
//#include <stack>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int maxn = 120005;
pair <double, double> v[maxn];
int pus[maxn];
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 sz = 0;
inline void push(int x)
{
    stk[++sz] = x;
    pus[x] = 1;
}

inline void pop()
{
    pus[stk[sz]] = 0;
    sz--;
}

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);
    push(1);
    for(int i = 2; i <= n; i++)
    {
        pair <double, double> x = v[stk[sz - 1]];
        pair <double, double> y = v[stk[sz]];
        while(sz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
        {
            pop();
            x = v[stk[sz - 1]];;
            y = v[stk[sz]];
        }
        push(i);
    }
    for(int i = n - 1; i >= 1; i--)
    {
        pair <double, double> x = v[stk[sz - 1]];
        pair <double, double> y = v[stk[sz]];
        if(!pus[i])
        {
            while(sz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
            {
                pop();
                x = v[stk[sz - 1]];;
                y = v[stk[sz]];
            }
            push(i);
        }
    }
    pair <int, int> x = v[stk[sz - 1]];
    pair <int, int> y = v[stk[sz]];
    while(sz >= 2 && !det(x.first, x.second, y.first, y.second, v[1].first, v[1].second))
    {
        pop();
        x = v[stk[sz - 1]];;
        y = v[stk[sz]];
    }
    out << sz << "\n";
    for(int i = 1; i <= sz; i++)
        out << setprecision(6) << fixed << v[stk[i]].first << " " << setprecision(6) << fixed << v[stk[i]].second << "\n";
    return 0;
}