Cod sursa(job #1301065)

Utilizator somuBanil Ardej somu Data 25 decembrie 2014 15:46:40
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

struct Point {
    double x, y;
};

#define nmax 120005
#define E 1e-12
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n;
Point A[nmax];

int i, len;
int st[nmax];
bool viz[nmax];

bool cmp(Point a, Point b) {
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

double det(Point O, Point A, Point B) {
    return (A.x - O.x)*(B.y - O.y)-(A.y - O.y)*(B.x - O.x);
}

void read() {
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> A[i].x >> A[i].y;
}

void convex_hull() {
    sort(A+1, A+n+1, cmp);
    
    st[1] = 1, st[2] = 2, len = 2;
    viz[1] = viz[2] = true;
    
    for (i = 3; i <= n; i++) {
        while (len > 1 && det(A[st[len-1]], A[st[len]], A[i]) < E)
            viz[st[len--]] = false;
        st[++len] = i;
        viz[i] = true;
    }
    
    for (i = n-1; i > 0; i--) {
        if (viz[i])
            continue;
        while (len > 1 && det(A[st[len-1]], A[st[len]], A[i]) < E)
            len--;
        st[++len] = i;
    }
    
    fout << len << "\n";
    fout << fixed;
    for (i = 1; i <= len; i++)
        fout << setprecision(6) << A[st[i]].x << " " << A[st[i]].y << "\n";
    
}

int main() {
    
    read();
    convex_hull();
    
    return 0;
}