Cod sursa(job #1934800)

Utilizator ciprianprohozescuProhozescu Ciprian ciprianprohozescu Data 21 martie 2017 20:25:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>
#define NMAX 120010

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct
{
    double x, y;
    friend bool operator < (punct a, punct b);
};

int n;
punct p, v[NMAX];
stack<punct> S;
vector<punct> sol;

bool operator < (punct a, punct b)
{
    return (a.y - p.y) * (b.x - p.x) < (a.x - p.x) * (b.y - p.y) ||
    ((a.y - p.y) * (b.x - p.x) == (a.x - p.x) * (b.y - p.y) &&
     (a.x - p.x) * (a.x - p.x) + (a.y - p.y) * (a.y - p.y) < (b.x - p.x) * (b.x - p.x) + (b.y - p.y) * (b.y - p.y));
}

void citire();
double arie(punct a, punct b, punct c);

int main()
{
    int i;
    citire();
    sort(v, v + n);
    S.push(v[0]);
    for (i = 1; i < n; i++)
    {
        //analizez vf stivei cu v[i] si v[i + 1]
        if (arie(S.top(), v[i], v[i + 1]) <= 0)
        {
            while (!S.empty())
            {
                v[i] = S.top();
                S.pop();
                if (arie(S.top(), v[i], v[i + 1]) > 0)
                    break;
            }
        }
        S.push(v[i]);
    }
    //afisare invers
    while (!S.empty())
    {
        sol.push_back(S.top());
        S.pop();
    }
    fout << sol.size() << '\n';
    fout << fixed << setprecision(13);
    for (i = sol.size() - 1; i >= 0; i--)
        fout << sol[i].x << ' ' << sol[i].y << '\n';
    fout.close();
    return 0;
}

void citire()
{
    int i;
    fin >> n;
    fin >> v[0].x >> v[0].y;
    p = v[0];
    for (i = 1; i < n; i++)
    {
        fin >> v[i].x >> v[i].y;
        if (v[i].x < p.x || (v[i].x == p.x && v[i].y < p.y))
            p = v[i];
    }
    //v[n] = v[0];
}
double arie(punct a, punct b, punct c)
{
    return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2;
}