Cod sursa(job #2276166)

Utilizator alextodoranTodoran Alexandru Raul alextodoran Data 4 noiembrie 2018 11:59:54
Problema Infasuratoare convexa Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

#define NM 120002
#define x first
#define y second

using namespace std;

int n;

pair <double, double> v[NM];
vector <pair <double, double> > infs;

bool u[NM];

double det(pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int main()
{
    ifstream fin ("infasuratoare.in");
    ofstream fout ("infasuratoare.out");
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1);
    infs.push_back(v[1]);
    infs.push_back(v[2]);
    for(int i = 3; i <= n; i++)
    {
        int l = infs.size();
        while(l > 1 && det(infs[l - 2], infs[l - 1], v[i]) < 0)
        {
            l--;
            infs.pop_back();
        }
        infs.push_back(v[i]);
    }
    for(int i = n - 1; i >= 2; i--)
        if(det(v[i], infs[0], infs[1]) > 0)
        {
            int l = infs.size();
            while(l > 1 && det(infs[l - 2], infs[l - 1], v[i]) < 0)
            {
                l--;
                infs.pop_back();
            }
            infs.push_back(v[i]);
        }
    fout << infs.size() << "\n";
    for(auto j : infs)
        fout << fixed << setprecision(12) << j.x << " " << j.y << "\n";
    fout << "\n";
    return 0;
}