Cod sursa(job #1409690)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 30 martie 2015 17:43:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

const int NMAX = 120005;
const double eps = 1e-12;

using namespace std;

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

struct puncte
{
    double x;
    double y;

    bool operator < (const puncte &t) const
    {
        if (t.x < x)
            return true;
        if (t.x > x)
            return false;
        if (t.y < y)
            return true;
        return false;
    }
};

int N;
vector <puncte> punct;
bool viz[NMAX];
int stiva[NMAX],top;

double cross_product(puncte O, puncte A, puncte B)
{
    return(A.x - O.x)*(B.y-O.y) - (B.x - O.x)*(A.y - O.y);
}

void solve(int pct)
{
    while(top >= 2 && cross_product(punct[stiva[top-1]],punct[stiva[top]],punct[pct]) < eps)
    {
        viz[ stiva[top] ] = false;
        top--;
    }
    top++;
    stiva[top] = pct;
    viz[ stiva[top] ] = true;
}

int main()
{
    f >> N;
    for (int i = 1; i <= N; ++i)
    {
        puncte pct;
        f >> pct.x >> pct.y;
        punct.push_back(pct);
    }

    sort(punct.begin(), punct.end());

    stiva[1] = 0;
    stiva[2] = 1;
    top = 2;
    viz[1] = 1;

    for (int i = 2; i < punct.size(); ++i)
    {
        if (!viz[i])
            solve(i);
    }
    for (int i = punct.size()-2; i >= 0; --i)
    {
        if(!viz[i])
            solve(i);
    }

    g << top-1 << '\n';
    for (int i = 1; i < top; ++i)
    {
        g << fixed << setprecision(12) << punct[stiva[i]].x << " " <<punct[stiva[i]].y << '\n';
    }

    f.close();
    g.close();
    return 0;
}