Cod sursa(job #1879150)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 14 februarie 2017 19:03:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

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

struct pct{double x, y;};
pct first;
int n;

double det(pct a, pct b, pct c)     {

    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cnd(pct a, pct b)      {

    return det(first, a, b) > 0;
}

int main()      {


    fin >> n;
    vector<pct> P(n+1);
    int i, poz = 1;
    for (i=1; i<=n; i++)
    {
        fin >> P[i].x >> P[i].y;
        if (P[i].x == P[poz].x)
            if (P[i].y < P[poz].y)
                poz = i;
        if (P[i].x < P[poz].x)
            poz = i;
    }


    P[0] = P[poz];
    first = P[0];
    swap(P[poz], P[n]);
    P.pop_back();
    sort(P.begin()+1, P.begin()+n, cnd);


    vector<int> S;
    S.push_back(0);
    S.push_back(1);

    for (i=2; i<n; i++)
    {
        while (S.size() > 1 && det(P[S[S.size()-2]], P[S[S.size()-1]], P[i]) <= 0)
            S.pop_back();
        S.push_back(i);
    }
    if  (S.size() > 1 && det(P[S[S.size()-2]], P[S[S.size()-1]], P[i]) <= 0)
        S.pop_back();
    fout << S.size() << '\n';
    for (i=0; i<S.size(); i++)
        fout << fixed << setprecision(6) << P[S[i]].x << " " << P[S[i]].y << '\n';

    return 0;
}