Cod sursa(job #1584004)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 29 ianuarie 2016 17:09:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
/* Graham's Scan (Andrew's version) */

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

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;

    double x, y;
    vector<pair<double, double>> points;

    for (i = 0; i < N; i++)
    {
        f >> x >> y;
        points.push_back(make_pair(x, y));
    }
    f.close();

    sort(points.begin(), points.end(), [] (const pair<double, double> &a, const pair<double, double> &b) -> bool
         {
             if (a.first == b.first)
                return a.second < b.second;
             return a.first < b.first;
         });


    vector<pair<double, double>> list1, list2;

    list1.push_back(points[0]);
    list1.push_back(points[1]);
    list2.push_back(points.back());
    list2.push_back(points[points.size() - 2]);

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

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

    ofstream g("infasuratoare.out");

    g << fixed << setprecision(12) << list1.size() + ((int)list2.size() - 2) << '\n';
    for (i = 0; i < list1.size(); i++)
        g << list1[i].first << ' ' << list1[i].second << '\n';
    for (i = 1; i < list2.size() - 1; i++)
        g << list2[i].first << ' ' << list2[i].second << '\n';
    g.close();

    return 0;
}