Cod sursa(job #2713804)

Utilizator AACthAirinei Andrei Cristian AACth Data 28 februarie 2021 17:19:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int Max = 1e5 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int n;
struct punct{
    long double x,y;
};
vector < punct > puncte;
vector < punct > sol;
long double deltax;
long double deltay;
punct P0;
int indice;
void retain_P0(punct p, int id)
{
    if(P0.x == p.x and P0.y > P0.y)
    {
        P0 = p;
        indice = id;
        return;
    }
    if(P0.x > p.x)
    {
        P0 = p;
        indice = id;
        return;
    }

}
void read()
{
    f>>n;
    int i;
    P0.x = 1e9 + 1;
    for(i=1;i<=n;i++)
    {
        long double x,y;
        f>>x>>y;
        retain_P0({x,y},i - 1);
        puncte.push_back({x,y});
    }

}
bool cmp(punct p1 , punct p2)
{
    if(p1.x == P0.x)
        return 0;
    if(p2.x == P0.x)
        return 1;
    long double slope1 = (p1.y - P0.y) / (p1.x - P0.x);
    long double slope2 = (p2.y - P0.y) / (p2.x - P0.x);
    return slope1 < slope2;
}
void show()
{
    g<<sol.size()<<'\n';
    for(auto it : sol)
        g<<fixed<<setprecision(12)<<it.x <<' '<<it.y <<'\n';
}
bool formeaza_concavitate(punct A, punct B, punct C)
{
    return ((B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) )  < 0;
}
void solve()
{
    sol.push_back(P0);
   puncte.erase(puncte.begin() + indice);
   //for(auto it : puncte)
   // cout<<it.x<<' '<<it.y<<'\n';
    sort(puncte.begin(),puncte.end(),cmp);
    sol.push_back(puncte[0]);
    int i;
    for(i=1;i < puncte.size();i++)
    {

        int last = sol.size();
        last --;
        while(sol.size() >= 2 and formeaza_concavitate(sol[last-1],sol[last],puncte[i]))
            sol.pop_back(),--last;
        sol.push_back(puncte[i]);
    }

    show();
}
void restart()
{

}

int32_t main()
{
    nos();
    read();
    solve();
    restart();

    return 0;
}