Cod sursa(job #2517198)

Utilizator trifangrobertRobert Trifan trifangrobert Data 3 ianuarie 2020 01:47:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 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);
}

vector < pair <double, double> > ConvexHull(vector < pair <double, double> > v)
{
    vector < pair <double, double> > stk;
    stk.push_back(v[0]);
    for (int i = 1;i < v.size();++i)
    {
        while (stk.size() >= 2 && det(stk[stk.size() - 2], stk.back(), v[i]) < 0)
            stk.pop_back();
        stk.push_back(v[i]);
    }
    return stk;
}

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 < pair <double, double> > under, over;
    under.push_back(points[0]);
    over.push_back(points[0]);
    for (int i = 1;i < points.size() - 1;++i)
        if (det(points[0], points[i], points.back()) >= 0)
            under.push_back(points[i]);
        else
            over.push_back(points[i]);
    under.push_back(points.back());
    over.push_back(points.back());
    reverse(over.begin(), over.end());
    auto hullunder = ConvexHull(under);
    auto hullover = ConvexHull(over);
    hullunder.pop_back();
    hullover.pop_back();
    vector < pair <double, double> > hull;
    for (auto &i : hullunder)
        hull.push_back(i);
    for (auto &i : hullover)
        hull.push_back(i);
    fout << hull.size() << "\n";
    fout << setprecision(12) << fixed;
    for (auto &i : hull)
        fout << i.first << " " << i.second << "\n";
    fin.close();
    fout.close();
    return 0;
}