Cod sursa(job #3207369)

Utilizator UengineDavid Enachescu Uengine Data 26 februarie 2024 00:16:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define dd double

using namespace std;

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

struct coord{
    dd x, y;
};

int n, poz;
coord pct0 = {1e9 + 5, 1e9 + 5};
vector <coord> v;
vector <coord> stak;

int cadran(coord pct){
    if(pct.y >= 0){
        if(pct.x >= 0)
            return 1;
        return 2;
    }
    if(pct.x < 0)
        return 3;
    return 4;
}

dd determinant(dd x1, dd y1, dd x2, dd y2, dd x3, dd y3){
    return x1 * (y2-y3) + x2 * (y3-y1) + x3 * (y1-y2);
}

bool cmp(coord a, coord b){
    double det = determinant(pct0.x, pct0.y,a.x,a.y,b.x,b.y);
    return det > 0;
}

void solve(){
    for(int i = 0; i < n; i++){
        if(v[i].x < pct0.x or (v[i].x == pct0.x and v[i].y < pct0.y)){
            pct0 = v[i];
            poz = i;
        }
    }
    swap(v[0], v[poz]);
    sort(v.begin() + 1, v.end(), cmp);
//    for(auto vec:v)
//        cout << vec.x << ' ' << vec.y << '\n';
    stak.push_back(v[0]);
    stak.push_back(v[1]);
    int len = 2;
    for(int i = 2; i < v.size(); i++) {
        while (stak.size() >= 2 and
               determinant(stak[len - 2].x, stak[len - 2].y, stak[len - 1].x, stak[len - 1].y, v[i].x, v[i].y) < 0){
            stak.pop_back();
            len--;
        }
        stak.push_back(v[i]);
        len++;
    }
}

int main()
{
    cin >> n;
    cout << fixed << setprecision(6);
    for(int i = 0; i < n; i++){
        double x, y;
        cin >> x >> y;
        v.push_back({x, y});
    }
    solve();
    cout << stak.size() << '\n';
    for(auto &i : stak)
        cout << i.x << ' ' << i.y << '\n';
//    while(!stak.empty()){
//        cout << stak.top().x << ' ' << st.top().y << '\n';
//        st.pop();
//    }
//    for(auto unghi:v)
//        cout << unghi.x << ' ' << unghi.y << '\n';
    return 0;
}