Cod sursa(job #1076674)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 10 ianuarie 2014 14:51:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 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++)
    {
        scanf("%f%f", &xf, &yf);
        v[i].x = (double)xf;
        v[i].y = (double)yf;
    }
    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);
}

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

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

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

    return 0;
}