Cod sursa(job #1545899)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 7 decembrie 2015 12:49:06
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#define MAXN 120000
using namespace std;

struct point{
    double x, y;
};
point pivot;
point v[MAXN + 1];
point sol[MAXN + 1];
point zero;
point S[MAXN + 1];

inline double dist(point A, point B) {
    return ((A.x - B.x) * (A.x - B.x)) + ((A.y - B.y) * (A.y - B.y));
}

inline double E(point A, point B, point C) {
    double k = ((B.x - A.x) * (C.y - A.y)) - ((C.x - A.x) * (B.y - A.y));
    return k;
}

inline bool cmp(point A, point B) {
    double x = E(pivot, A, B);
   // if (x == 0)
     //   return (dist(pivot, A) < dist(pivot, B));
    return (x < 0);
}

inline bool trigo(point A, point B) {
    double x = E(A, B, zero);
    return (x > 0);
}

int main () {
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");

    int n;
    cin >> n;
    pivot.y = 1000000000;
    pivot.x = 1000000000;

    for (int i = 0 ; i < n ; ++i) {
        cin >> v[i].x >> v[i].y;
        if (v[i].y < pivot.y || (v[i].y == pivot.y && v[i].x < pivot.x))
            pivot = v[i];
    }

    sort(v, v + n, cmp);

    S[0] = v[0];
    int ps = 0;
    for (int i = 1 ; i < n ; ++i) {
        while (ps > 0 && E(S[ps - 1], S[ps], v[i]) > 0)
            --ps;
        ++ps;
        S[ps] = v[i];
    }

    ++ps;
   // sort(S, S + ps, trigo);
    cout << ps << "\n";
    for (int i = ps - 1 ; i >= 0 ; --i)
        cout << S[i].x << " " << S[i].y << "\n";

    return 0;
}