Cod sursa(job #2526202)

Utilizator CiboAndreiAndrei Cibo CiboAndrei Data 18 ianuarie 2020 12:28:28
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>

using namespace std;

//#define f cin
//#define g cout

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

const int dim = 101;

int n;

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

vector <str> st;

inline int 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){
    /*if(a.tg != b.tg)
        return a.tg < b.tg;
    if(a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;*/
    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 + 1, v + n + 1, cond);
}

int main(){
    int i;

    f >> n;

    for(i = 1; i <= n; ++i){
        f >> v[i].x >> v[i].y;
        if(v[i].y == 0)
            v[i].tg = 1111111111;
        else v[i].tg = (double)v[i].x / v[i].y;
    }

    sortare_input();

    for(i = 1; i <= n; ++i){
        g << v[i].x << " " << v[i].y << '\n';
    }

    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]);

        if(intoarcere == 0){
            st.pop_back();
            st.push_back(v[i]);
        } else if(intoarcere < 0){
            st.push_back(v[i]);
        } else {
            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';

    for(auto it: st)
        g << it.x << " " << it.y << '\n';

    return 0;
}