Cod sursa(job #1115717)

Utilizator Theorytheo .c Theory Data 21 februarie 2014 23:22:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <stack>
#include <iomanip>
#include <algorithm>

using namespace std;

#define Point pair<double, double>
#define x first
#define y second

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

const double eps = 0.0000000000001;
const int NMAX = 120009;

Point V[NMAX]; int N; Point S[NMAX];

double sarrus(const Point& A, const Point& B, const Point& C){
    double a = A.y - B.y;
    double b = B.x - A.x;
    double c = A.x * B.y - A.y * B.x;

    return a * C.x + b * C.y + c;
}

bool cmp(const Point& A, const Point& B) {
    return sarrus(V[1], A, B) < 0 ;
}

int main() {

    fin >> N; int ind = 1;

    for(int i = 1; i <= N; ++i) {

        fin >> V[i].x >> V[i].y;
        if(V[i] < V[ind]) ind = i;
    }

    swap(V[ind], V[1]);

    sort(V + 2, V + 1 + N, cmp);

    S[1] = V[1]; S[2] = V[2];
    int sz = 2;
    for(int i = 3; i <= N; ++i) {

        while(sz >= 2 && sarrus(S[sz - 1], S[sz], V[i]) > 0) sz--;

        S[++sz] = V[i];
    }
    fout << fixed ;
    fout << sz <<'\n';
    for(int i = sz; i ; --i)
        fout << setprecision(6) << S[i].x << " " << S[i].y <<'\n';


    return 0;
}