Cod sursa(job #1369037)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 2 martie 2015 21:16:28
Problema Infasuratoare convexa Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

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

    bool cmp1(punct a, punct b)
    {
        if(a.y < b.y) return true;
        if(a.y > b.y) return false;
        return a.x > b.x;
    }

    bool cmp2(punct a, punct b)
    {
        if(a.y > b.y) return true;
        if(a.y < b.y) return false;
        return a.x < b.x;
    }

    bool operator == (punct a, punct b)
    {
        return a.x == b.x && a.y == b.y;
    }

inline double det(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);
}

vector<punct> v;
punct pct[120010];
int n;

void citire()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%lf%lf", &pct[i].x, &pct[i].y);
}

void solve()
{
    sort(pct, pct+n, cmp1);

    for(int i = 0; i < n; i++)
    {
        while(v.size() >= 2 && det(v[v.size()-2], v[v.size()-1], pct[i]) < -0.00000001)
            v.pop_back();
        v.push_back(pct[i]);
    }

    sort(pct, pct+n, cmp2);
    for(int i = 0; i < n; i++)
    {
        while(v.size() >= 2 && det(v[v.size()-2], v[v.size()-1], pct[i]) < -0.00000001
              || v[v.size()-1] == pct[i])
            v.pop_back();
        v.push_back(pct[i]);
    }

    if(v.back() == v.front())
        v.pop_back();
}

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

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

    citire();
    solve();
    afisare();

    return 0;
}