Cod sursa(job #2427537)

Utilizator PrekzursilAndrei Visalon Prekzursil Data 31 mai 2019 23:15:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define INF 1500000000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i;
pair<double, double> v[120005],sol[120005];
double det(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp(pair<double, double> a, pair<double, double> b)
{
    double d = det(make_pair(0, 0), a, b);
    if (d == 0)
        return a.x*a.x+a.y*a.y > b.x*b.x+b.y*b.y;
    else
        return d > 0;
}
int main()
{
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> v[i].x >> v[i].y;
    int punctmin = 0; double minimy = INF; double minimx = INF;
    for (i=1; i<=n; i++)
        if (v[i].y < minimy)
        {
            minimy = v[i].y;
            minimx = v[i].x;
            punctmin = i;
        }
        else
            if (v[i].y == minimy)
                if (v[i].x < minimx)
                {
                    minimx = v[i].x;
                    punctmin = i;
                }
    double xx = v[punctmin].x; double yy = v[punctmin].y;
    for (i=1; i<=n; i++)
    {
        v[i].x -= xx;
        v[i].y -= yy;
    }
    swap(v[1], v[punctmin]);
    sort(v+2, v+n+1, cmp);
    int ind = 0;
    for (i=3; i<=n; i++)
        if (det(v[1], v[2], v[i]) != 0)
        {
            ind = i;
            break;
        }
    ind--;
    if (ind > 2)
        for (i=2; i<=(ind+1)/2; i++)
            swap(v[i], v[ind-i+2]);
    sol[1] = v[1];
    sol[2] = v[2];
    int k = 2;
    for (i=3; i<=n; i++)
    {
        while (k >= 2 && det(sol[k-1], sol[k], v[i]) < 0)
            k--;
        sol[++k] = v[i];
    }
    fout << k << "\n";
    for (i=1; i<=k; i++)
    {
        fout << setprecision(6) << fixed << sol[i].x+xx << " ";
        fout << setprecision(6) << fixed << sol[i].y+yy << "\n";
    }
    return 0;
}