Cod sursa(job #1997343)

Utilizator vladm98Munteanu Vlad vladm98 Data 3 iulie 2017 22:55:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

struct punct
{
    long double x, y;
} v[120005];
vector<punct> solve;
long double determinant (long double x1, long double y1, long double x2, long double y2, long double x3, long double y3)
{
    return x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1;
}
class cmp
{
public:
    bool operator () (const punct &a, const punct &b) const
    {
        if (determinant(v[0].x, v[0].y, a.x, a.y, b.x, b.y)>0) return 1;
        if (determinant(v[0].x, v[0].y, a.x, a.y, b.x, b.y)<0) return 0;
        return a.x < b.x;
    }
};
int main()
{
    ifstream fin ("infasuratoare.in");
    ofstream fout ("infasuratoare.out");
    int n;
    fin >> n;
    fin >> v[0].x >> v[0].y;
    for (int i = 1; i<n; ++i)
    {
        fin >> v[i].x >> v[i].y;
        if (v[i].x < v[0].x || (v[i].x==v[0].x && v[i].y < v[0].y))
            swap (v[0], v[i]);
    }
    v[n] = v[0];
    sort (v+1, v+n, cmp());
    solve.push_back(v[0]);
    for (int i = 1; i<=n; ++i)
    {
        bool verif = 1;
        while (solve.size()>=2 && verif)
        {
            verif = 0;
            punct alfa = solve.back();
            solve.pop_back();
            if (determinant(solve.back().x, solve.back().y, alfa.x, alfa.y, v[i].x, v[i].y) <= 0)
                verif = 1;
            else solve.push_back(alfa);
        }
        solve.push_back(v[i]);
    }
    solve.pop_back();
    fout << solve.size() << '\n';
    for (auto x:solve)
        fout << setprecision(8) << fixed << x.x << " " << x.y << '\n';
    return 0;
}