Cod sursa(job #3286778)

Utilizator lolismekAlex Jerpelea lolismek Data 14 martie 2025 17:31:59
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

#include <iomanip>

#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define pii pair <int, int>

#define fr first 
#define sc second

using namespace std;

string filename = "infasuratoare";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

////////////////////////////////////////////////////////////

const int NMAX = 120000;

struct Point{
    double x, y;
}v[NMAX + 1];

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

double Area(Point p1, Point p2, Point p3){
    return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
}

void solve(){
    int n;
    fin >> n;

    for(int i = 1; i <= n; i++){
        fin >> v[i].x >> v[i].y;
    }

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

    vt <Point> top, bttm; 

    top.pb(v[1]);
    bttm.pb(v[1]);
    for(int i = 2; i <= n; i++){
        while(sz(top) >= 2 && Area(top[sz(top) - 2], top.back(), v[i]) <= 0){
            top.pop_back();
        }
        top.pb(v[i]);

        while(sz(bttm) >= 2 && Area(bttm[sz(bttm) - 2], bttm.back(), v[i]) >= 0){
            bttm.pop_back();
        }
        bttm.pb(v[i]);
    }

    fout << fixed << setprecision(12);

    for(auto X : top){
        fout << X.x << ' ' << X.y << '\n';
    }

    for(int i = sz(bttm) - 2; i >= 1; i--){
        fout << bttm[i].x << ' ' << bttm[i].y << '\n';
    }
}

int main(){

    int T;
    //fin >> T;

    T = 1;

    while(T--){
        solve();
    }

    return 0;
}