Cod sursa(job #1581663)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 26 ianuarie 2016 23:39:59
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
/* Jarvis' march */

#include <fstream>
#include <cmath>
#include <vector>
#include <utility>
#include <ctime>
#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()
{
    srand(time(NULL));

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

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

    int extremeIndex = 0;
    for (i = 0; i < N; i++)
    {
        f >> x >> y;
        points.push_back(make_pair(x, y));
        if (points[i].second < points[extremeIndex].second)
            extremeIndex = i;
        else if (points[i].second == points[extremeIndex].second && points[i].first < points[extremeIndex].first)
            extremeIndex = i;
    }
    f.close();

    vector<pair<double, double>> sol;
    bool valid = true;
    sol.push_back(points[extremeIndex]);

    int pivot;
    while (valid)
    {
        do
        {
            pivot = rand() % points.size();
        } while (pivot == extremeIndex);

        for (i = 0; i < points.size(); i++)
            if (getDet3(points[extremeIndex], points[pivot], points[i]) < 0)
                pivot = i;

        if (points[pivot] != sol[0])
        {
            sol.push_back(points[pivot]);
            extremeIndex = pivot;
        }
        else
            valid = false;

    }

    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;
}