Cod sursa(job #1211066)

Utilizator mariusn01Marius Nicoli mariusn01 Data 21 iulie 2014 22:40:22
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <algorithm>

#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;

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

int cmp(pair<double, double> a, pair<double, double> b) {
    return det(make_pair(0, 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].second < V[pminim].second || ( (V[i].second == V[pminim].second )&&(V[i].first < V[pminim].first ) ))
            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";
    for (i=1;i<=k;i++)
        fout<<V[ S[i] ].first + aux.first<<" "<<V[ S[i] ].second + aux.second<<"\n";


    return 0;
}