Cod sursa(job #2465861)

Utilizator bogdan2604Bogdan Dumitrescu bogdan2604 Data 30 septembrie 2019 22:54:07
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
#include <bits/stdc++.h>

using namespace std;
typedef double dbl;

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

int sz,i;
dbl x,y;
vector <pair<dbl,dbl>> v;
stack <pair<dbl,dbl>> stk,stk_afis;
pair<dbl,dbl> punct_inceput;

int distsq(pair<dbl,dbl> a, pair<dbl,dbl> b)
{
    return (b.first - a.first)*(b.first - a.first) + (b.second - a.second)*(b.second - a.second);
}

int orientation(pair<dbl,dbl> a, pair<dbl,dbl> b, pair<dbl,dbl> c)
{
    int slope_final = (b.second - a.second)*(c.first - b.first) - (c.second - b.second)*(b.first - a.first);
    if(!slope_final)
        return 0; //! coliniare;
    return slope_final > 0 ? 1 : 2; //! dreapta : stanga
}

void aflare_punct()
{
    pair <dbl,dbl> pct = v[0];
    int poz = 0;

    for(i = 1; i < sz; ++ i)
        if(v[i].second < pct.second)
            pct = v[i], poz = i;
        else if(v[i].second == pct.second && v[i].first < pct.first)
            pct = v[i], poz = i;
    swap(v[0],v[poz]);
}
bool cmp(pair <dbl,dbl> a, pair <dbl,dbl> b)
{
    int orn = orientation(punct_inceput,a,b);
    if(!orn)
        return distsq(punct_inceput,a) < distsq(punct_inceput,b);
    return orn == 2 ? 1 : 0;

}
pair<dbl,dbl> stktop_minus_unu()
{
    pair <dbl,dbl> a = stk.top();
    stk.pop();
    pair <dbl,dbl> b = stk.top();
    stk.push(a);
    return b;
}
int main()
{
    ios::sync_with_stdio(0);
    f >> sz;
    for(i = 0; i < sz; ++ i)
    {
        f >> x >> y;
        v.push_back({x,y});
    }
    aflare_punct();
    punct_inceput = v[0];
    v.erase(v.begin());
    -- sz;
    sort(v.begin(), v.end(), cmp);
    i = 1;
    /*infasurare.push_back(punct_inceput);
     dawhile(i < sz)
    {
        while(i < sz - 1 orientation(punct_inceput,v[i],v[i + 1]))
            ++i;
        infasurare.push_back(v[i]);
    }
    //! if(infasurare.size() < 3) nu este posibila infasurarea daca raman doar 3 puncte
    //! dar nu este cazul in problema asta
    */
    stk.push(punct_inceput);
    stk.push(v[0]);
    stk.push(v[1]);
    for(i = 3; i < sz; ++ i)
    {
        while(orientation(stktop_minus_unu(),stk.top(),v[i]) == 1)
            stk.pop();
        stk.push(v[i]);
    }
    int a = stk.size();
    int b = a;
    g << a << '\n';
    while(a)
    {
        stk_afis.push(stk.top());
        stk.pop();
        -- a;
    }
    while(b)
    {
        g << stk_afis.top().first << ' ' << stk_afis.top().second << '\n';
        stk_afis.pop();
        -- b;
    }

}