Cod sursa(job #1581600)

Utilizator sulzandreiandrei sulzandrei Data 26 ianuarie 2016 22:11:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
/* O(N^3) algorithm */

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

using namespace std;

const double INF_DOUBLE = numeric_limits<double>::max();

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];
    pair<double, double> center(INF_DOUBLE, INF_DOUBLE);
    int pos = 1;
    for (i = 0; i < N; i++)
    {
        f >> points[i].first >> points[i].second;
        if (points[i].second < center.second)
            center = points[i],pos=i;
        else if (points[i].second == center.second && points[i].first < center.first)
            center = points[i],pos=i;
    }
    f.close();
    swap(points[0],points[pos]);

    sort(points+1, points+ N, [&] (const pair<double, double> &a, const pair<double, double> &b) {
        /*double angleA = atan2(a.second - center.second, a.first - center.first);
        double angleB = atan2(b.second - center.second, b.first - center.first);

        if (angleA == angleB)
        {
            return sqrt((a.first - center.first) * (a.first - center.first)
                         + (a.second - center.second * a.second - center.second)) <
                    sqrt((b.first - center.first) * (b.first - center.first)
                         + (b.second - center.second) * (b.second - center.second));
        }

        return angleA < angleB;*/
        return getDet3(center, 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';
    //g << points[0].first << ' ' << points[0].second << '\n';
    for (auto it = sol.begin(); it != sol.end(); it++)
        g << it->first << ' ' << it->second << '\n';
    g.close();
    return 0;
}