Cod sursa(job #3194191)

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

using namespace std;

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

const int N_MAX = 120005;
const double INF = 1e9;

struct Point {

    double x, y;

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

};

int n;
Point v[N_MAX];
vector<Point> ans;

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

bool compare(Point &a, Point &b) {
    return (triangleArea(v[0], a, b) > 0);
}

void solve(){

    cin >> n;

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

    sort(v + 1, v + n, compare);

    ans.push_back(v[0]);

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

    cout << ans.size() << '\n';
    for(auto it : ans){
        cout << fixed << setprecision(6) << it.x << " " << it.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;
}