Cod sursa(job #1644972)

Utilizator BaweeLazar Vlad Bawee Data 10 martie 2016 10:29:00
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
//Conex Hull Andrew's Algorithm
//Complexity: O(n*logn)
//Implementation time:
#include <fstream>
#include <algorithm>
#include <iomanip>

#define x first
#define y second

using namespace std;

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

const double epsilon = 1e-12;
typedef pair<double , double> point;
point points[120001];

bool viz[120001];
int stiva[120001];
int n , top;

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

int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i) f >> points[i].first >> points[i].second;

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

    for(int i = 1; i <= n; i++)
    {
        if(viz[i]) continue;
        while(top >= 2 && crossProduct(points[stiva[top - 1]] , points[stiva[top]] , points[i]) < epsilon)
            viz[stiva[top--]] = false;
        stiva[++top] = i;
        viz[i] = true;
    }

    for(int i = n - 1 , t = top + 1; i >= 1; i--)
    {
        if(viz[i]) continue;
        while(top >= t && crossProduct(points[stiva[top - 1]] , points[stiva[top]] , points[i]) < epsilon)
            viz[stiva[top--]] = false;
        stiva[++top] = i;
        viz[i] == true;
    }

    g << top << "\n";

    g << fixed << setprecision(6);

    for(int i = 1; i <= top; i++) g << points[stiva[i]].first << " " << points[stiva[i]].second << "\n";


    return 0;
}