Cod sursa(job #1335099)

Utilizator raulmuresanRaul Muresan raulmuresan Data 4 februarie 2015 23:38:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const int MAXN = 120009;

struct punct {
    double x, y;
}v[MAXN];

int N, top;
punct stack[MAXN];

inline double CrossProduct(punct A, punct B, punct C) {
   // return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
   return ( double ) A.x*B.y + B.x*C.y + C.x*A.y - A.y*B.x - B.y*C.x - C.y*A.x;
}

struct cmp {
    bool operator()(const punct &A, const punct &B) const {
        return CrossProduct(v[0], A, B) > 0;//"left turn", so we have to change the order
    }
};

void Read() {
    fin >> N;
    int poz = 0;
    for (int i = 0; i < N; ++i) {
        fin >> v[i].x >> v[i].y;
        if (v[poz].y > v[i].y)//saves the lowest point, or in case of equality, the most right one
            poz = i;
        if (v[poz].y == v[i].y && v[poz].x > v[i].x)
            poz = i;
    }
    swap(v[0], v[poz]);
}

void ConvexHull() {
    //sorts the points increasingly according to the slopes between the fixed point and another point
    sort(v + 1, v + N, cmp());
    stack[0] = v[0];
    stack[1] = v[1];
    top = 1;
    for (int i = 2; i < N; ++i) {
        while (top >= 1 && CrossProduct(stack[top - 1], stack[top], v[i]) < 0)
            --top;
        stack[++top] = v[i];
    }
}

void Write() {
    fout << top + 1 << '\n';
    fout << setprecision(6) << fixed;
    for (int i = 0; i <= top; ++i)
        fout << stack[i].x << ' ' << stack[i].y << '\n';
}

int main() {
    Read();
    ConvexHull();
    Write();
    fin.close();
    fout.close();
    return 0;
}