Cod sursa(job #1644234)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 9 martie 2016 22:08:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
# include <cstdio>
# include <vector>
# include <algorithm>
# define pb push_back
# define po pop_back
# define pc pair<double, double>
# define x  first
# define y  second
using namespace std;

FILE *fin = fopen("infasuratoare.in", "rt");
FILE *fout = fopen("infasuratoare.out", "wt");

int n, k;

pc mn;
vector<pc> v, s;

bool comp(pc a, pc b) {
    return ((a.y-mn.y)*(b.x-mn.x) < (b.y-mn.y)*(a.x-mn.x));
}

bool semn(pc a, pc b, pc c) {
    return (((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)) <= 0);
}

int main() {
    if (fscanf(fin, "%d", &n)) ;

    pc A;
    mn.x = mn.y = 1e9;

    for (int i=0; i<n; ++i) {
        if (fscanf(fin, "%lf%lf", &A.x, &A.y)) ;
        if ((mn.y > A.y) || ((mn.y == A.y) && (mn.x > A.x))) {
            mn = A;
            k = i;
        }
        v.pb(A);
    }

    swap(v[k], v.back());
    v.po();
    sort(v.begin(), v.end(), comp);

    s.pb(mn);
    s.pb(v[0]);
    s.pb(v[1]);
    for (unsigned i=2; i<v.size(); ++i) {
        while (semn(s[s.size()-2], s[s.size()-1], v[i]))
            s.po();
        s.pb(v[i]);
    }

    fprintf(fout, "%d\n", s.size()) ;
    for (unsigned i=0; i<s.size(); ++i)
        fprintf(fout, "%lf %lf\n", s[i].x, s[i].y);
    return 0;
}