Cod sursa(job #1189243)

Utilizator japjappedulapPotra Vlad japjappedulap Data 21 mai 2014 22:14:20
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip>
using namespace std;

#define IN "infasuratoare.in"
#define OU "infasuratoare.out"
#define x first
#define y second

ifstream is (IN);
ofstream os (OU);

int N, H = 2;
pair <float, float> S[120005], V[120005];
pair <float, float> P, M(1000000000, 1000000000);

inline float CMP( const pair<float, float>& A, const pair<float, float>& B );
double CROSS(pair<float, float>& A, pair<float, float>& B, pair<float, float>& C);

int main()
{
    ///*** READ ***///
    is >> N;
    int pos;
    for (int i = 1; i <= N; ++i)
    {
        is >> P.x >> P.y;
        if (P < M)
            M = P, pos = i;
        V[i] = P;
    }
    ///*** SORT ***///
    swap (V[1], V[pos]);
    sort (V+2, V+N+1, CMP);
    ///*** Convex Hull ***///
    S[1] = V[1];
    S[2] = V[2];
    for (int i = 3; i <= N; ++i)
    {
        while (H >= 2 && CROSS(S[H-1], S[H], V[i]) < 0)
            --H;
        S[++H] = V[i];
    }
    os << H << '\n';
    for (int i = 2; i <= H; ++i)
        os << fixed << S[i].x << ' ' << S[i].y << '\n';
    os << fixed << S[1].x << ' ' << S[1].y << '\n';
    is.close();
    os.close();
}

double CROSS(pair<float, float>& A, pair<float, float>& B, pair<float, float>& C){
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
};

inline float CMP( const pair<float, float>& A, const pair<float, float>& B ){
    return (A.x - M.x) * (B.y - M.y) > (B.x - M.x) * (A.y - M.y);
}