Cod sursa(job #2517200)

Utilizator trifangrobertRobert Trifan trifangrobert Data 3 ianuarie 2020 02:10:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

double det(pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
    return (a.first * b.second + b.first * c.second + c.first * a.second) - (b.second * c.first + c.second * a.first + a.second * b.first);
}

bitset <120005> seen;

int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int N;
    fin >> N;
    vector < pair <double, double> > points(N);
    for (auto &p : points)
        fin >> p.first >> p.second;
    sort(points.begin(), points.end());
    vector <int> stk;
    stk.push_back(0);
    for (int i = 1;i < points.size();++i)
    {
        while (stk.size() >= 2 && det(points[stk[stk.size() - 2]], points[stk.back()], points[i]) < 0)
        {
            seen[stk.back()] = false;
            stk.pop_back();
        }
        stk.push_back(i);
        seen[i] = true;
    }
    for (int i = points.size() - 1;i >= 0;--i)
    {
        if (seen[i] == 1)
            continue;
        while (stk.size() >= 2 && det(points[stk[stk.size() - 2]], points[stk.back()], points[i]) < 0)
        {
            seen[stk.back()] = false;
            stk.pop_back();
        }
        stk.push_back(i);
        seen[i] = true;
    }
    stk.pop_back();
    fout << stk.size() << "\n";
    fout << setprecision(12) << fixed;
    for (auto &i : stk)
        fout << points[i].first << " " << points[i].second << "\n";
    fin.close();
    fout.close();
    return 0;
}