Submission #967271

#	Time	Username	Problem	Language	Result	Execution time	Memory
967271		v_matei	Mobile (BOI12_mobile)	C++17	100 / 100	956 ms	63932 KiB

mobile

        #include <bits/stdc++.h>
        #include <cmath>
        #include <iomanip>
         
        #define ll long long
        #define ull unsigned long long
        #define pdd std::pair<double, double>
         
        #define NMAX 1e6
        #define INF 2e9
         
        struct Tower {
          double x, y;
        };
        struct Seg {
          double st, fn;
        };
        double n, l;
        std::vector<Tower> s;
         
        void citire() {
          std::cin >> n >> l;
          s.resize(n);
          for (int i = 0; i < n; i++) {
            std::cin >> s[i].x >> s[i].y;
          }
        }
         
        double b_search(double lo, double hi, std::function<bool(double)> f) {
          for (int i = 1; hi - lo > 0.001; i++) {
            double mid = (lo + hi) / 2;
            if (f(mid))
              hi = mid;
            else
              lo = mid;
          }
          return lo;
        }
         
        bool find_point(double k) {
          std::vector<Seg> segs;
          for (Tower &it : s) {
            if (k * k < it.y * it.y)
              continue;
            double max_dx = sqrt(k * k - it.y * it.y);
            segs.push_back({it.x - max_dx, it.x + max_dx});
            if (segs.back().st < 0 && segs.back().fn > l)
              return 1;
          }
          double pre = 0;
          for (Seg &it : segs) {
            if (pre >= l)
              return 1;
            if (pre >= it.st)
              pre = std::max(pre, it.fn);
          }
          return pre > l;
        }
         
        int main() {
          std::ios::sync_with_stdio(0);
          std::cin.tie(0);
          std::cout.tie(0);
          citire();
          double k = b_search(0, INF, find_point);
          std::cout << std::fixed << std::setprecision(10) << k;
          return 0;
        }

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5