Cod sursa(job #1899455)

Utilizator giotoPopescu Ioan gioto Data 2 martie 2017 19:13:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int n, f[120005];
struct punct{
    double x, y;
}p[120005];
vector <int> stiva;
inline bool cmp(punct x, punct y){
    if(x.x != y.x) return x.x < y.x;
    return x.y < y.y;
}
inline double Arie(punct a, punct b, punct c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i)
        scanf("%lf%lf", &p[i].x, &p[i].y);
    sort(p + 1, p + n + 1, cmp);
    stiva.push_back(1);
    stiva.push_back(2);
    f[2] = 1;
    for(int i = 1; i <= n ; ++i){
        while(stiva.size() > 1 && Arie(p[stiva[stiva.size() - 2]], p[stiva[stiva.size() - 1]], p[i]) <= 0)
            f[stiva[stiva.size() - 1]] = 0,stiva.pop_back();
        stiva.push_back(i);
        f[i] = 1;
    }
    for(int i = n; i >= 1 ; --i){
        if(f[i] == 1) continue ;
        while(stiva.size() > 1 && Arie(p[stiva[stiva.size() - 2]], p[stiva[stiva.size() - 1]], p[i]) <= 0)
            f[stiva[stiva.size() - 1]] = 0,stiva.pop_back();
        stiva.push_back(i);
        f[i] = 1;
    }
    printf("%d\n", stiva.size() - 1);
    for(int i = 1; i < stiva.size() ; ++i)
        printf("%f %f\n", p[stiva[i]].x, p[stiva[i]].y);
    return 0;
}