Cod sursa(job #3194180)

Utilizator not_anduAndu Scheusan not_andu Data 17 ianuarie 2024 11:15:34
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("03")

using namespace std;

#define INFILE "infasuratoare.in"
#define OUTFILE "infasuratoare.out"

const double INF = 1e9;

struct Point {
    
    double x;
    double y;

    Point() : x(0), y(0) {}
    Point(double _x, double _y) : x(_x), y(_y) {}

};

int n;
Point minim(INF, INF);
vector<Point> v;

bool comp(Point a, Point b){
    return (-minim.x + a.x) * (minim.y + b.y) > (-minim.y + a.y) * (-minim.x * b.x);
}

double determinant(Point &a, Point &b){
    return (a.x * b.y - a.y * b.x);
}

int orientation(Point &a, Point &b, Point &c){

    double ans = determinant(a, b) + determinant(b, c) + determinant(c, a);

    if(ans < 0) return -1;
    else if(ans == 0) return 0;
    return 1;

}

void solve(){

    cin >> n;
    v.resize(n);

    for(int i = 0; i < n; ++i){
        double x, y; cin >> x >> y; v[i] = Point(x, y);
        if(v[i].y < minim.y){
            minim = Point(v[i].x, v[i].y);
            swap(v[0], v[i]);
        }
    }

    sort(v.begin() + 1, v.end(), comp);

    // for(auto it : v){
    //     cout << fixed << setprecision(6) << it.x << " " << it.y << '\n';
    // }
    // cout << "============" << '\n';

    vector<Point> ans;
    ans.push_back(v[0]), ans.push_back(v[1]);

    for(int i = 2; i < n; ++i){
        while(ans.size() > 1 && orientation(ans[ans.size() - 2], ans[ans.size() - 1], v[i]) != -1){
            ans.pop_back();
        }
        ans.push_back(v[i]);
    }

    cout << ans.size() << '\n';
    for(auto nr : ans){
        cout << fixed << setprecision(6) << nr.x << " " << nr.y << '\n';
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}