Cod sursa(job #963880)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 19 iunie 2013 17:01:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
 
#define x first
#define y second
#define sz size
#define add push_back
#define L S.sz()-1
#define erase pop_back
 
typedef double ld;
typedef pair <ld, ld> punct;
typedef vector <punct> poligon;
 
poligon P, S;
int n;
 
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
 
inline ld cross(punct A, punct B, punct C) {
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
 
inline bool cmp (punct A, punct B) {
    return cross(P[0], A, B) < 0;
}
 
int main() {
    fin >> n;
    int pos = 0;
    for (int i = 0; i < n; ++i) {
        punct p;
        fin >> p.x >> p.y;
        P.add(p);
        if (P[pos] > P[i])
            pos = i;
    }
    swap (P[pos], P[0]);
    poligon :: iterator it = P.begin();
    it++;
    sort(it, P.end(), cmp);
    S.add (P[0]);
    S.add (P[1]);
    for (int i = 2; i < n; ++i) {
        while (S.sz() > 1 && cross (S[L-1], S[L], P[i]) > 0) {
            S.erase();
        }
        S.add (P[i]);
    }
    fout << fixed << S.sz() << "\n";
    for (int i = L; i >= 0; --i)
        fout << setprecision(9) << S[i].x << " " << S[i].y << "\n";
    fout.close();
    return 0;
}