Cod sursa(job #2029631)

Utilizator Coroian_DavidCoroian David Coroian_David Data 30 septembrie 2017 12:16:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>

#define MAX_N 120000

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct coord
{
    long double x, y;
    int i;
};

int n, rez;
coord v[MAX_N + 1];
coord cvx[MAX_N + 1];

coord mn;

long double poz(long double x)
{
    if(x < 0.0D)
        return -x;

    return x;
}

const long double epsilon = 0.000000000001D;

void readFile()
{
    f >> n;

    mn = {2000000000.0D, 0.0D, 0};

    int i;
    for(i = 1; i <= n; i ++)
    {
        f >> v[i].x >> v[i].y;
        v[i].i = i;

        if(v[i].x < mn.x || (poz(v[i].x - mn.x) == epsilon && v[i].y < mn.y))
            mn = v[i];
    }

    f.close();
}

long double ccw(coord a, coord b, coord c)
{
    ///x1 y1
    ///x2 y2
    ///x1*y2 - x2*y1;

    return (a.x * b.y - b.x * a.y +
            b.x * c.y - c.x * b.y +
            c.x * a.y - a.x * c.y
            )/2.0D;
}

struct cmp
{
    bool operator () (coord a, coord b)
    {
        long double aria = ccw(mn, a, b);

        return aria > 0.0D;
    }
};

void solve()
{
    if(mn.i != 1)
    {
        coord aux = v[1];
        v[1] = mn;
        v[mn.i] = aux;
    }

    sort(v + 2, v + n + 1, cmp());

    rez = 2;
    cvx[1] = v[1];
    cvx[2] = v[2];

    int i;
    for(i = 3; i <= n; i ++)
    {
        while(rez >= 2 && ccw(cvx[rez - 1], cvx[rez], v[i]) < 0.0D)
            rez --;

        cvx[++ rez] = v[i];
    }
}

void printFile()
{
    g << rez << "\n";

    int i;
    for(i = 1; i <= rez; i ++)
        g << fixed << setprecision(6) << cvx[i].x << " " << cvx[i].y << "\n";

    g << "\n";

    g.close();
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}