Cod sursa(job #3269969)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 21 ianuarie 2025 17:11:44
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<stack>
#define INF 999999999
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
struct point{
    double x, y;
};
int n;
std::vector<point>v;
inline double det(point a, point b, point c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(point a, point b){
    point aux={0, 0};
    double d=det(aux, a, b);
    return (d>0);
};
int main()
{
    std::stack<point>ans;
    point min={INF, INF};
    fin>>n;
    v=std::vector<point>(n);
    for(int i=0; i<n; ++i)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].y<min.y || v[i].y==min.y && v[i].x<min.x)
            min=v[i];
    }
    for(int i=0; i<n; ++i)
    {
        v[i].x-=min.x;
        v[i].y-=min.y;
    }
    std::sort(v.begin()+1, v.end(), cmp);
    ans.push(v[0]);
    ans.push(v[1]);
    for(int i=2; i<n; ++i)
    {
        point a{}, b{};
        b=ans.top();
        ans.pop();
        a=ans.top();
        while(det(a, b, v[i])<0)
        {
            b=ans.top();
            ans.pop();
            a=ans.top();
        }
        ans.push(b);
        ans.push(v[i]);
    }
    std::vector<point>sol;
    while(!ans.empty())
    {
        point local=ans.top();
        local.x+=min.x;
        local.y+=min.y;
        sol.push_back(local);
        ans.pop();
    }
    for(int i=sol.size()-1; i>=0; --i)
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}