Cod sursa(job #1581620)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 26 ianuarie 2016 22:25:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
/* Graham's scan */

#include <fstream>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>
#include <iomanip>

using namespace std;

double getDet3(const pair<double, double> &p1,
               const pair<double, double> &p2,
               const pair<double, double> &p3)
{
    return p1.first * (p2.second - p3.second) +
            p2.first * (p3.second - p1.second) +
            p3.first * (p1.second - p2.second);
}

int main()
{
    int N, i;
    ifstream f("infasuratoare.in");
    f >> N;

    pair<double, double> points[N];

    int centerIndex = 0;
    for (i = 0; i < N; i++)
    {
        f >> points[i].first >> points[i].second;
        if (points[i].second < points[centerIndex].second)
            centerIndex = i;
        else if (points[i].second == points[centerIndex].second && points[i].first < points[centerIndex].first)
            centerIndex = i;
    }
    f.close();

    swap(points[0], points[centerIndex]);
    centerIndex = 0;

    sort(points + 1, points + N, [&] (const pair<double, double> &a, const pair<double, double> &b) {
         return getDet3(points[centerIndex], a, b) > 0;
     });

     vector<pair<double, double>> sol;
     sol.push_back(points[0]);
     sol.push_back(points[1]);

     for (i = 2; i < N; i++)
     {
         while (sol.size() > 2 && getDet3(sol[sol.size() - 2], sol.back(), points[i]) <= 0)
            sol.pop_back();
        sol.push_back(points[i]);
     }

    ofstream g("infasuratoare.out");

    g << fixed << setprecision(12) << sol.size() << '\n';
    for (auto it = sol.begin(); it != sol.end(); it++)
        g << it->first << ' ' << it->second << '\n';
    g.close();

    return 0;
}