Cod sursa(job #1796054)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 3 noiembrie 2016 01:49:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <vector>
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(pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
    double x1 = x.first;
    double y1 = x.second;
    double x2 = y.first;
    double y2 = y.second;
    double x3 = z.first;
    double y3 = z.second;
    return ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) >= 0;
}

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 sz = 1;
    stk[1] = 1;
    pus[1] = 1;

    for(int i = 2; i <= n; i++)
    {
        while(sz >= 2 && !det(v[stk[sz - 1]], v[stk[sz]], v[i]))
        {
            pus[stk[sz]] = 0;
            sz--;
        }
        pus[i] = 1;
        stk[++sz] = i;
    }
    for(int i = n - 1; i >= 1; i--)
    {
        if(pus[i] == 1)
            continue;
        while(sz >= 2 && !det(v[stk[sz - 1]], v[stk[sz]], v[i]))
        {
            pus[stk[sz]] = 0;
            sz--;
        }
        pus[i] = 1;
        stk[++sz] = i;
    }
    while(sz >= 2 && !det(v[stk[sz - 1]], v[stk[sz]], v[1]))
    {
        pus[stk[sz]] = 0;
        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;
}