Cod sursa(job #3309932)

Utilizator alexbaldovin20alex baldovin alexbaldovin20 Data 10 septembrie 2025 15:24:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

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

class Point
{
    public:
        long double x,y;
        bool operator<(const Point &other)
        {
            if(this->x==other.x)
                return this->y<other.y;
            return this->x<other.x;
        }
};

int n;
vector<Point> v;

long double cross_product(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)
{
    return cross_product(v[1],A,B)<0;
}

int main()
{
    in>>n;
    v.resize(n + 5);
    for(int i=1;i<=n;i++)
        in>>v[i].x>>v[i].y;
    int p=1;
    for(int i=2;i<=n;i++)
        if(v[i]<v[p])
            p=i;
    swap(v[1],v[p]);
    sort(v.begin()+2,v.begin()+n+1,cmp);
    vector<Point>s;
    s.push_back(v[1]);
    s.push_back(v[2]);
    for(int i=3;i<=n;i++)
    {
        while(s.size()>1 && cross_product(s[s.size()-2],s[s.size()-1],v[i])>0)
            s.pop_back();
        s.push_back(v[i]);
    }
    out<<s.size()<<"\n";
    out<<fixed<<setprecision(7);
    for(int i=s.size()-1;i>=0;i--)
        out<<s[i].x<<" "<<s[i].y<<"\n";
}