Cod sursa(job #1211104)

Utilizator mariusn01Marius Nicoli mariusn01 Data 21 iulie 2014 23:20:09
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define DIM 120010

using namespace std;

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

vector< pair<double, double> > V;
int S[DIM];

int n, i, k, pminim;
double x, y;

double det(const pair<double, double> &a, const pair<double, double> &b, const pair<double, double> &c) {
    return  (b.first-a.first) * (c.second-a.second) -
            (b.second-a.second) * (c.first-a.first);
}

int cmp(const pair<double, double> &a, const pair<double, double> &b) {
    return det(V[0], a, b) >= 0;
}

int main() {
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>x>>y;
        V.push_back(make_pair(x, y));
    }

    pminim = 0;
    for (i=1;i<V.size();i++)
        if (V[i]< V[pminim])
            pminim = i;



    pair<double, double> aux = V[pminim];
    V[pminim] = V[0];
    V[0] = aux;

    for (i=0;i<V.size(); i++) {
        V[i].first -= aux.first;
        V[i].second -= aux.second;
    }

    sort(V.begin()+1, V.end(), cmp);
/*
    for (i=0;i<n;i++)
        fout<<V[i].first<<" "<<V[i].second<<"\n";
*/



    S[1] = 0;
    S[2] = 1;
    k = 2;
    for (i=2;i<V.size(); i++) {
        while (k >= 2 && det(V[ S[k-1] ], V[ S[k] ], V[i])<=0)
            k--;
        S[++k] = i;
    }

    fout<<k<<"\n";
    fout<<fixed;
    for (i=1;i<=k;i++)
        fout<<setprecision(9) <<V[ S[i] ].first + aux.first<<" "<<V[ S[i] ].second + aux.second<<"\n";


    return 0;
}