Cod sursa(job #2027815)

Utilizator Coroian_DavidCoroian David Coroian_David Data 26 septembrie 2017 18:57:34
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 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;

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 || (v[i].x == mn.x && 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;
}

bool cmp(coord a, coord b)
{
    if(a.i == mn.i)
        return 1;///a < b

    long double aria = ccw(mn, a, b);

    return aria > 0;
}

void solve()
{
    sort(v + 1, 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)
            rez --;

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

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

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

    g << "\n";

    g.close();
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}