Cod sursa(job #1148972)

Utilizator lorundlorund lorund Data 21 martie 2014 13:01:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int N;
double x, y;
vector<pair<double, double> > v, stack;
pair<double, double> minim;

void read(){
    scanf("%d", &N);
    scanf("%lf %lf", &x, &y);
    minim = make_pair(x,y);

    for (int i=1; i<N; ++i){
        pair<double, double> point;
        scanf("%lf %lf", &x, &y);

        point = make_pair(x, y);
        if (minim < point){
            v.push_back(point);
        }
        else{
            v.push_back(minim);
            minim = point;
        }
    }
}

bool comp(pair<double, double> first, pair<double, double> second){
    return minim.first*first.second+first.first*second.second+second.first*minim.second-
            second.first*first.second-first.first*minim.second-minim.first*second.second > 0;
}

bool trig_ord(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3){
    return p1.first*p2.second+p2.first*p3.second+p3.first*p1.second-
            p3.first*p2.second-p2.first*p1.second-p1.first*p3.second > 0;
}

void solve(){
    stack.push_back(minim);
    stack.push_back(v[0]);

    for (unsigned i=1; i<v.size();){
        if (trig_ord(stack[stack.size()-2], stack[stack.size()-1], v[i])){
            stack.push_back(v[i]);
            ++i;
        }
        else{
            stack.pop_back();
        }
    }
}

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

    read();
    sort(v.begin(), v.end(), comp);
    v.push_back(minim);
    solve();
    printf("%d\n", stack.size()-1);
    for (int i=0, l=stack.size()-1; i<l; ++i){
        printf("%lf %lf\n", stack[i].first, stack[i].second);
    }
    return 0;
}