Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- #include <map>
- #include <queue>
- #include <math.h>
- #define ll long long
- #define ld long double
- #define pll pair<ll, ll>
- using namespace std;
- const double eps = 0.0001;
- ll xl, xr, r, n, xi, yi;
- vector<pll> pillars;
- class Graph {
- public:
- vector<vector<ll>> adj;
- Graph(int v) {
- adj.resize(v);
- }
- void addEdge(int u, int w) {
- adj[u].push_back(w);
- }
- };
- // R - радіус вазона, з яким ми хочемо пройти
- bool canFit(pll firstP, pll secondP, ld R) {
- return sqrt(pow(secondP.first - firstP.first, 2) + pow(secondP.second - firstP.second, 2)) - 2 * r > R * 2;
- }
- // тут ми проходимося по колонам і дивимося де ми не можемо пройти між колонами або стінами
- // і будуємо граф з тих колон між якими не можна пройти
- bool checkGraph(ld R, ll s, ll e) {
- Graph g(n + 2);
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (i != j && !canFit(pillars[i], pillars[j], R)) {
- g.addEdge(i, j);
- }
- }
- if (pillars[i].first - r - xl <= R * 2) {
- g.addEdge(i, n);
- g.addEdge(n, i);
- }
- if (pillars[i].first + r + R * 2 >= xr) {
- g.addEdge(i, n + 1);
- g.addEdge(n + 1, i);
- }
- }
- //перевіряємо чи є шлях від лівої до правої стіни
- vector<bool> used(g.adj.size());
- queue<ll> q;
- used[s] = true;
- q.push(s);
- while (!q.empty()) {
- ll cur = q.front();
- q.pop();
- for (ll i : g.adj[cur]) {
- if (!used[i]) {
- q.push(i);
- used[i] = true;
- if (i == e) return true;
- }
- }
- }
- return false;
- }
- //бінарним пошуком ми просто перебираємо який радіус нам підійде для того аби пройти
- ld binSrch() {
- ld lt = 0;
- ld rt = abs(xr) + abs(xl);
- while (rt - lt > eps) {
- ld m = (rt + lt) / 2;
- bool smaller = checkGraph(m, n, n + 1);
- if (smaller) rt = m;
- else lt = m;
- }
- return lt;
- }
- int main()
- {
- cin >> xl >> xr; // координати лівої та правої стін коридору
- cin >> r; // радіус колон у коридорі
- cin >> n; // кількість колон
- pillars.resize(n);
- for (int i = 0; i < n; i++) {
- cin >> xi >> yi;
- pillars[i].first = xi;
- pillars[i].second = yi;
- }
- cout << binSrch() * 2;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement