Cod sursa(job #1166829)

Utilizator muresan_bogdanMuresan Bogdan muresan_bogdan Data 3 aprilie 2014 20:51:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const double INF = 1000000000;

struct pct{
    double x, y;
};

int n, i, k;
pct v[120002], o, sol[120002];

double cross(pct A, pct B, pct C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

bool cmp(pct a, pct b) {
    if(cross(o, a, b) < 0) {
        return false;
    }
    return true;
}

int main() {
    fin >> n;
    o.x = o.y = INF;
    for(i = 0; i < n; i++) {
        fin >> v[i].x >> v[i].y;
        if(v[i].x <= o.x) {
            if(v[i].x == o.x) {
                if(v[i].y < o.y) {
                    o.y = v[i].y;
                    k = i;
                }
            }else {
                o.x = v[i].x;
                o.y = v[i].y;
                k = i;
            }
        }
    }
    swap(v[0], v[k]);
    sort(v + 1, v+n, cmp);
    sol[0] = v[0];
    sol[1] = v[1];
    int nr = 1;
    for(i = 2; i < n; i++) {
        while(cross(sol[nr-1], sol[nr], v[i]) < 0) {
            nr--;
        }
        nr++;
        sol[nr] = v[i];
    }
    fout << nr + 1 << '\n';
    for(i = 0; i <= nr; i++) {
        fout << fixed << setprecision(6) << sol[i].x << ' ' << sol[i].y << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}