Cod sursa(job #2477893)

Utilizator richard26Francu Richard richard26 Data 21 octombrie 2019 11:49:00
Problema Combinari Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.04 kb
#include <bits/stdc++.h>

using namespace std;

pair <float, float> bottom_point;

int orient(pair<float, float> p1, pair<float, float> p2, pair<float, float> p3) {

    int s = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second - p3.first * p2.second - p1.first * p3.second - p2.first * p1.second;

    if (s == 0) {
        return 0;
    }

    if (s < 0) {
        return 1;
    }

    return 2;
}

int dist(pair<int, int> p1, pair <int, int> p2)
{
    return (p1.first - p2.first)*(p1.first - p2.first) +
          (p1.second - p2.second)*(p1.second - p2.second);
}

bool cmp(pair<float, float> p1, pair<float, float> p2) {
    int o = orient(bottom_point, p1, p2);

    if (o == 0) {
        return (dist(bottom_point, p1) >= dist(bottom_point, p2) ) ? -1:1;

    }

    return (o == 2)? -1:1;

}

int main()
{
    vector< pair<float, float> > hull;
    vector< pair<float, float> > points;

    cin >> bottom_point.first >> bottom_point.second;
    points.push_back(bottom_point);
    for (int i = 0; i < 3; i++) {
        pair <float, float> p;
        cin >> p.first >> p.second;
        points.push_back(p);
        if (p.second < bottom_point.second) {
            bottom_point = p;
        } else if (p.second == bottom_point.second && p.first < bottom_point.first) {
            bottom_point = p;
        }
    }
    int pos = -1;
    bool ok = true;
    for (pair <float, float> it : points) {
        pos ++;
        if (it == bottom_point) {
                pair<float, float> aux;
                aux = points[pos];
                points[pos] = points[0];
                points[0] = aux;
                ok = false;
        }
    }

    sort(points.begin() + 1, points.end(), cmp());


    stack <pair<float, float>> st;
    st.push(points[0]);
    st.push(points[1]);

    for (int i = 2; i < 3; i++) {
        while (st.size() >= 2 && orient(st[st.size() - 2], st[st.size() - 1], points[i])) {
            st.pop();
        }

        st.push(points[i])
    }

    vector <pair <float, float> > points1;
    for (pair<int, int> it : points) {
            bool ok = true;
        for (pair<float, float> it1 : st) {
            if (it1 == it) {
                ok = false;
            }
        }

        if (ok) {
            points1.push_back(it);
        }
    }

    if (st.size() == 2) {
        cout << st[0].first << " " << st[0].second << " si " << points1[0].first << " " << points1[0].second << endl;
        cout << st[1].first << " " << st[1].second << " si " << points1[1].first << " " << points1[1].second << endl;
    }
    else if(st.size() == 3) {
        cout << st[0].first << " " << st[0].second << " ";

        cout << st[1].first << " " << st[1].second << " ";

        cout << st[2].first << " " << st[2].second << endl;

        cout << points1[0].first << " " << points1[0].second;

    } else {
        for (pair<float, float> it : st) {
            cout << it.first << " " << it.second << endl;
        }
    }

    return 0;
}