Cod sursa(job #3292318)

Utilizator vladsoartavlad sofronea vladsoarta Data 7 aprilie 2025 21:10:15
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define double long double
using namespace std;

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

int n,i;
struct point{
double x,y;
bool operator <(point b)const{
    if(x!=b.x)
        return x < b.x;
    return y < b.y;
}
}v[100001];

double cross_product(const point& A, const point& B, const 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)//sortare panta
{
    return cross_product(v[1],a,b)< 0;
}

int main()
{
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+1+n);
    sort(v+2,v+1+n,cmp);

    vector<int>stk;
    stk.push_back(1);
    stk.push_back(2);
    for(i=3;i<=n;i++){
        while(stk.size() > 2 && cross_product(v[stk[stk.size()-2]],v[stk[stk.size()-1]],v[i]) > 0){
            stk.pop_back();
        }
        stk.push_back(i);
    }
    cout<<stk.size()<<'\n';
    for(int h=0;h<stk.size();h++)
        cout<<fixed<<setprecision(9)<<v[stk[h]].x<<" "<<v[stk[h]].y<<'\n';
    return 0;
}