Cod sursa(job #3036374)

Utilizator SmauSmau George Robert Smau Data 24 martie 2023 11:49:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.2 kb
#include <bits/stdc++.h>

#define NMAX 120008

using namespace std;

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

class Point {
    private:
        double x, y;

    public:
        friend istream& operator >>(istream& in, Point& p) {
            in >> p.x >> p.y;
            return in;
        }

        friend ostream& operator <<(ostream& out, const Point& p) {
            out << fixed << setprecision(12) << p.x << ' ' << p.y;
            return out;
        }

        friend bool operator < (const Point &a, const Point &b) {
            if(a.x == b.x) return a.y < b.y;
            return a.x < b.x;
        }

        friend Point operator - (const Point &a, const Point &b) {
            Point ans;
            ans.x = a.x - b.x;
            ans.y = a.y - b.y;

            return ans;
        }

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

vector <Point> Build(vector <Point> p) {
    vector <Point> half;
    for(auto A : p) {
        while(half.size() >= 2) {
            Point B = half[half.size() - 1];
            Point C = half[half.size() - 2];

            if((A - C) * (B - C) < 0) break; 

            half.pop_back();
        }

        half.push_back(A);
    }

    return half;
}

vector <Point> v;
int n;

int main() {
    fin >> n;
    for(int i = 1; i <= n; i ++) {
        Point p; fin >> p;
        v.push_back(p);
    }

    sort(v.begin(), v.end());
    vector <Point> bot_half = Build(v);
    // for(auto x : bot_half) fout << x << '\n';
    // fout << "\n\n";

    reverse(v.begin(), v.end());
    vector <Point> top_half = Build(v);
    // for(auto x : top_half) fout << x << '\n';
    // fout << "\n\n";
    
    reverse(bot_half.begin(), bot_half.end());
    reverse(top_half.begin(), top_half.end());
    bot_half.pop_back();
    top_half.pop_back();
    reverse(bot_half.begin(), bot_half.end());
    reverse(top_half.begin(), top_half.end());

    fout << top_half.size() + bot_half.size() << '\n';

    for(auto x: bot_half) fout << x << '\n';
    for(auto x: top_half) fout << x << '\n';
    

    return 0;
}