Cod sursa(job #1614068)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 25 februarie 2016 19:46:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define f first
#define s second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int S[120050], n, i, k;
vector<pair<double, double> > points(120050);
vector<int> infConvex;

double sarrus(int x, int y, int z) {
    double yur, prk;
    yur = (points[x].f * points[y].s + points[y].f * points[z].s + points[z].f * points[x].s);
    prk = (points[x].f * points[z].s + points[y].f * points[x].s + points[z].f * points[y].s);

    return yur - prk;
}

int main()
{
    fin>>n;
    for (i = 0 ; i < n ; i++) {
        fin>>points[i].f>>points[i].s;
    }
    sort(points.begin() , points.begin() + n);
    k = -1;

    for (i = 0 ; i < n ; i++) {
        while (k >= 1 && sarrus(S[ k - 1 ], S[ k ], i) > 0)
            k--;
        S[ ++k ] = i;
    }
    for (i = 0 ; i <= k ; i++) {
        infConvex.push_back(S[i]);
    }
    k = -1;

    for (i = n - 1 ; i >= 0 ; i--) {
        while (k >= 1 && sarrus(S[ k - 1 ], S[ k ], i) > 0)
            k--;
        S[ ++k ] = i;
    }
    for (i = 1 ; i < k ; i++) {
        infConvex.push_back(S[i]);
    }

    fout<<infConvex.size();
    fout<<setprecision(6)<<fixed;
    for (i = infConvex.size() - 1 ; i >= 0 ; i--)
        fout<<'\n'<<points[infConvex[i]].f<<' '<<points[infConvex[i]].s;

    return 0;
}