Cod sursa(job #894125)

Utilizator vgabi94Vaduva Gabriel vgabi94 Data 26 februarie 2013 19:52:24
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define x first
#define y second

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

const int maxn = 120001;
typedef pair<double, double> Point;

Point v[maxn];
Point stack[maxn];
int N;

inline int ccw(const Point& p1, const Point& p2, const Point& p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

inline bool cmp(const Point &p1, const Point &p2)
{
    return ccw(v[1], p1, p2) < 0;
}

void sortPoints()
{
    int pos = 1;
    for (int i = 2; i <= N; i++)
        if (v[i] < v[pos])
            pos = i;
    swap(v[1], v[pos]);
    sort(v+2, v+N+1, cmp);
}

int main()
{
    in >> N;
    for (int i = 1; i <= N; i++)
        in >> v[i].x >> v[i].y;
    sortPoints();
    int top = 2;
    stack[1] = v[1];
    stack[2] = v[2];
    for (int i = 3; i <= N; i++)
    {
        while (top >= 2 && ccw(stack[top], stack[top-1], v[i]) < 0) --top;
        stack[++top] = v[i];
    }
    out << top << '\n';
    out.setf(ios::fixed);
    out.precision(9);
    for (int i = top; i > 0; i--)
        out << stack[i].x << ' ' << stack[i].y << '\n';

    return 0;
}