Cod sursa(job #2203569)

Utilizator Menage_a_011UPB Cheseli Neatu Popescu Menage_a_011 Data 12 mai 2018 17:58:45
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.33 kb
// https://goo.gl/fBmFxu
#include <bits/stdc++.h>
using namespace std;

#define NMAX        120009
#define MMAX        200009
#define kInf        (1 << 30)
#define kInfLL      (1LL << 60)
#define kMod        666013
#define edge pair<int, int>
#define x first
#define y second

// number of tests from "in"
int test_cnt = 1;
void clean_test();

// your global variables are here
int N, posMin = 1, stackSz = 0;
pair <double, double> points[NMAX], st[NMAX];

double crossedProd(const pair <double, double> &a, const pair <double, double> &b, const pair <double, double> &c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool cmp(const pair <double, double> &p1, const pair <double, double> &p2) {
    return crossedProd(points[1], p1, p2) < 0;
}

// your solution is here
void solve() {
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> points[i].first >> points[i].second;
        
        if (points[i].first < points[posMin].first) {
            posMin = i;
        } else if (points[i].first < points[posMin].first && points[i].second < points[posMin].second) {
            posMin = i;
        }
    }
    
    swap(points[1], points[posMin]);
    sort(points + 1, points + N + 1, cmp);
    
    st[++stackSz] = points[1];
    st[++stackSz] = points[2];
    
    for (int i = 3; i <= N; ++i) {
        while (stackSz > 1 && crossedProd(st[stackSz - 1], st[stackSz], points[i]) > 0) {
            --stackSz;
        }
        
        st[++stackSz] = points[i];
    }
    
    cout << stackSz << '\n';
    cout << fixed << setprecision(6);
    for (int i = stackSz; i > 0; --i) {
        cout << st[i].first << ' ' << st[i].second << '\n';
    }
    
    if (test_cnt > 0) {
        clean_test();
    }
}

void clean_test() {
    
}

int main() {
    // din cauza ca fac redirectari, salvez starea lui cin si cout
    auto cin_buff = cin.rdbuf();
    auto cout_buff = cout.rdbuf();

    // las liniile urmatoare daca citesc din fisier
    ifstream fin("infasuratoare.in");
    cin.rdbuf(fin.rdbuf()); // save and redirect

    // las liniile urmatoare daca afisez in fisier
    ofstream fout("infasuratoare.out");
    cout.rdbuf(fout.rdbuf()); // save and redirect

//     cin >> test_cnt;
    while (test_cnt--) {
        solve();
    }

    // restore pentru cin si cout
    cin.rdbuf(cin_buff);
    cout.rdbuf(cout_buff);

    return 0;
}