Cod sursa(job #3323620)

Utilizator andreiaramaArama Andrei Robert andreiarama Data 18 noiembrie 2025 21:36:37
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

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

struct Vector2 {
    long double x, y;
    Vector2(long double x, long double y) {
        this->x=x;
        this->y=y;
    }
    Vector2();
    Vector2 operator+(Vector2 vec) {
        return Vector2(this->x+vec.x, this->y+vec.y);
    }
    Vector2 operator-(Vector2 vec) {
        return Vector2(this->x-vec.x, this->y-vec.y);
    }
    long double operator*(Vector2 vec) {
        return this->x*vec.y-this->y*vec.x;
    }
    static bool order(Vector2 a, Vector2 b, Vector2 c) {
        return ((c-b)*(a-b))<=0;
    }
};

bool cmp(const Vector2 &a, const Vector2 &b) {
    if(a.x==b.x) return a.y<b.y;
    return a.x < b.x;
}

vector<Vector2> hull;
vector<Vector2> a;
int n;
bool added[120001];
int main() {
    Vector2 current(0, 0);
    cin>>n;
    for(int i=0;i<n;i++) {
        cin>>current.x>>current.y;
        a.push_back(current);
    }
    sort(a.begin(), a.end(), cmp);
    for(int i=0;i<n;i++) {
        while(hull.size()>=2 && Vector2::order(a[i], hull.back(), hull[hull.size()-2])) {
            hull.pop_back();
        }
        hull.push_back(a[i]);
    }
    size_t lower_size=hull.size();
    for(int i=n-1;i>=0;i--) {
        while(lower_size<hull.size() && hull.size()>=2 && Vector2::order(a[i], hull.back(), hull[hull.size()-2])) {
            hull.pop_back();
        }
        hull.push_back(a[i]);
    }
    hull.pop_back();
    cout<<hull.size()<<'\n';
    for(auto pos:hull) {
        cout<<setprecision(6)<<fixed<<pos.x<<' '<<pos.y<<'\n';
    }
    return 0;
}