Cod sursa(job #1398982)

Utilizator deneoAdrian Craciun deneo Data 24 martie 2015 14:43:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;

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

struct point {
    double x, y;

    bool operator < (const point &b) {
        if (x == b.x)
            return y < b.y;
        return x < b.x;
    }
};

const int MAXN = 120001;

int n;
point v[MAXN + 10];
vector<point> top, bottom;

double cross (point a, point b, point c) {
    return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}

int main() {
    fin >> n;

    for (int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1);

    for (int i = 1; i <= n; ++i) {
        while (top.size() >= 2 && cross(*(top.end() - 1), *(top.end() - 2), v[i]) <= 0)
            top.pop_back();
        top.push_back(v[i]);
    }

    for (int i = n; i >= 0; --i) {
        while (bottom.size() >= 2 && cross(*(bottom.end() - 1), *(bottom.end() - 2), v[i]) <= 0)
            bottom.pop_back();
        bottom.push_back(v[i]);
    }

    fout << top.size() + bottom.size() << "\n";

    for (auto it: top)
        fout << it.x << " " << it.y << "\n";
    for (auto it: bottom)
        fout << it.x << " " << it.y << "\n";

    return 0;
}