Cod sursa(job #1076706)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 10 ianuarie 2014 15:08:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

struct punct
{
    double x, y;
    punct(double x = 0, double y = 0): x(x), y(y)
    {

    }
}v[120010];

int n;
vector<int> stiva;
int viz[120010];

double dist(punct a, punct b)
{
    return sqrt(1.*(a.x-b.x)*(a.x-b.x) + 1.*(a.y-b.y) * (a.y-b.y));
};

double determ(punct a, punct b, punct c)
{
    return a.x*(b.y - c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
}

struct cmp
{
    bool operator()(punct a, punct b)
    {
        if(a.y < b.y)
            return true;
        if(a.y == b.y && a.x < b.x)
            return true;
        return false;
    }
};

void citire()
{
    scanf("%d", &n);
    float xf, yf;
    for(int i = 0; i < n; i++)
    {
        cin >> v[i].x >> v[i].y;
    }
    sort(v, v+n, cmp());
}

void adaug(int x)
{
    punct a, b, c;
    c = v[x];
    if(stiva.size() >= 2)
    {
        a = v[stiva[stiva.size() - 2]];
        b = v[stiva[stiva.size() - 1]];
        while(determ(a, b, c) <= 0)
        {
            viz[stiva.back()] = 0;
            stiva.pop_back();
            if(stiva.size() >= 2)
            {
                a = v[stiva[stiva.size() - 2]];
                b = v[stiva[stiva.size() - 1]];
            }
            else
                break;
        }
    }

    stiva.push_back(x);
    viz[x] = 1;
}

void infas()
{
    int i;
    for(i = 0; i < n; i++)
        adaug(i);
    for(i--;i >= 0; i--)
        if(viz[i] == 0)
            adaug(i);
    adaug(0);
    stiva.pop_back();
}

void afisare()
{
    printf("%d\n", stiva.size());
    for(int i = 0; i < stiva.size(); i++)
        cout<<fixed<<v[stiva[i]].x<<' '<<v[stiva[i]].y<<"\n";
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    citire();
    infas();
    afisare();

    return 0;
}