Cod sursa(job #3348817)

Utilizator Matei_AndronacheMatei Andronache Matei_Andronache Data 24 martie 2026 11:41:28
Problema Infasuratoare convexa Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct point{
long double x,y,tg;
};
long double delta(point a,point b,point c)
{
    return b.x*c.y+c.x*a.y+a.x*b.y-b.x*a.y-c.x*b.y-a.x*c.y;
}
bool cmp(point a,point b)
{
    if (a.tg==b.tg)
    {
        if (a.x==b.x)
            return a.y<b.y;
        return a.x<b.x;
    }
    return a.tg<b.tg;
}
vector <point> convexhull(vector <point> v)
{
    point mn={1e18,1e18,67};
    for (int i=0;i<v.size();i++)
    {
        if (mn.y>v[i].y || (mn.y==v[i].y && mn.x>v[i].x))
        {
            mn=v[i];
        }
    }
    for (int i=0;i<v.size();i++)
    {
        if (mn.x==v[i].x && mn.y==v[i].y)
        {
            v.erase(v.begin()+i);
            break;
        }
    }
    for (int i=0;i<v.size();i++)
    {
        v[i].tg=atan2(v[i].y-mn.y,v[i].x-mn.x);
    }
    sort(v.begin(),v.end(),cmp);
    vector <point> st;
    st.push_back(mn);
    for (int i=0;i<v.size();i++)
    {
        while (st.size()>1 && delta(st[st.size()-2],st[st.size()-1],v[i])<=0)
        {
            st.pop_back();
        }
        st.push_back(v[i]);
    }
    return st;
}
int main()
{
    vector <point> v;
    int n;
    in>>n;
    v.resize(n);
    for (int i=0;i<n;i++)
    {
        in>>v[i].x>>v[i].y;
        //out<<v[i].x<<" "<<v[i].y<<'\n';
    }
    out<<fixed<<setprecision(30);
    v=convexhull(v);
    out<<v.size()<<'\n';
    for (int i=0;i<v.size();i++)
    {
        out<<v[i].x<<" "<<v[i].y<<'\n';
    }
    return 0;
}