Cod sursa(job #1131656)

Utilizator vlad.rusu11Rusu Vlad vlad.rusu11 Data 28 februarie 2014 23:07:30
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

#define x first
#define y second

#define NMax 12001

typedef pair<double,double> Point;

int N;
Point v[NMax];

Point stack[NMax];
int head;

void read()
{
    ifstream fin("infasuratoare.in");

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

inline double cross_product(const Point& A, const Point& B, const Point& C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

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

void sort_points()
{
    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);
}

void convex_hull()
{
    sort_points();

    stack[1] = v[1];
    stack[2] = v[2];
    head = 2;
    for(int i = 3 ; i <= N ; ++i)
    {
        while(head >= 2 && cross_product(stack[head - 1], stack[head], v[i]) > 0)
            --head;
        stack[++head] = v[i];
    }
}

void write()
{
    ofstream fout("infasuratoare.out");
    fout << fixed;
    fout << head << '\n';
    for(int i = head ; i >= 1 ; --i)
        fout << setprecision(9) << stack[i].x << ' ' << stack[i].y << '\n';
    fout.close();
}

int main()
{
    read();
    convex_hull();
    write();

    return 0;
}