Cod sursa(job #3233600)

Utilizator Vlad.Vlad Cristian Vlad. Data 3 iunie 2024 23:36:57
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <cmath>


#define INF 99999999999.0

using namespace std;

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

struct pct {
    double x, y;
    double cos;
};

vector<pct> v;
pct jos;

void read() {
    int N;
    jos.x = INF;
    jos.y = INF;
    jos.cos = 0;
    fin >> N;
    v.resize(N);
    for (int i = 0; i < N; ++i) {
        fin >> v[i].x >> v[i].y;
        if (jos.y > v[i].y) {
            jos = v[i];
        }
        else if (jos.y == v[i].y){
            if (jos.x < v[i].x) {
                jos = v[i];
            }
        }
    }
}

double calc_cos(pct a, pct b) {

    if (a.x == b.x && a.y == b.y) {
        return INF;
    }

    return (b.x - a.x) / sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

void complete_cos() {
    for (size_t i = 0; i < v.size(); ++i) {
        v[i].cos = calc_cos(v[i], jos);
    }
}

bool comp(pct a, pct b) {
    return a.cos < b.cos;
}

double dist(pct a, pct b) {
    return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}

double cross_product(pct a, pct b, pct c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

pct second_to_top(stack<pct> &s) {
    pct tp = s.top();
    s.pop();
    pct tp2 = s.top();
    s.push(tp);
    return tp2;
}

int main()
{
    read();
    complete_cos();
    sort(v.begin(), v.end(), comp);
    stack<pct> st;

    vector<pct> puncte;
    for (auto &punct : v) {
        if (!puncte.empty() && puncte.back().cos == punct.cos) {
            if (dist(jos, punct) > dist(jos, puncte.back())) {
                puncte.pop_back();
            }
        }
        puncte.push_back(punct);
    }

    for (auto &punct : puncte) {
        while (st.size() >= 2 && cross_product(second_to_top(st), st.top(), punct) <= 0) {
            st.pop();
        }
        st.push(punct);
    }

    vector<pct> ans;
    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }
    reverse(ans.begin(), ans.end());
    fout << ans.size() << "\n";
    for (auto& p : ans) {
        fout << fixed << setprecision(6) << p.x << " " << p.y << "\n";
    }

    return 0;
}