Cod sursa(job #2528595)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 22 ianuarie 2020 10:44:19
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

//ifstream f("date.in");
//ofstream g("date.out");

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int dim = 120005;

int n;

struct str{
    double x, y;
}v[dim];

vector <str> st;

inline double semn(str p1, str p2, str p3){
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

bool cond(str a, str b){
    return semn(v[1], a, b) < 0;
}

bool operator < (str a, str b){
    if(a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

void sortare_input(){
    int pos = 1;
    for (int i = 2; i <= n; ++i)
        if (v[i] < v[pos])
            pos = i;
    swap(v[1], v[pos]);

    sort(v + 2, v + n + 1, cond);
}

int main(){
    int i;

    f >> n;

    for(i = 1; i <= n; ++i){
        f >> v[i].x >> v[i].y;
    }

    sortare_input();

    st.push_back(v[1]);
    st.push_back(v[2]);

    for(i = 3; i <= n; ++i){
        int last = st.size() - 1;
        int intoarcere = semn(st[last - 1], st[last], v[i]);

        while (intoarcere >= 0 && last > 1){
            st.pop_back();
            --last;
            intoarcere = semn(st[last - 1], st[last], v[i]);
        }

        st.push_back(v[i]);
    }

    g << st.size() << '\n';

    g << fixed << setprecision(6);

    for(int i = st.size() - 1; i >= 0; --i){
        str it = st[i];
        g << it.x << " " << it.y << '\n';
    }

    ///M-AM SATURAT DEJA CEAPA EI DE PROBLEMA

    return 0;
}