Submission #1176666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176666		shangkuei	Mobile (BOI12_mobile)	C++17	100 / 100	291 ms	16072 KiB

mobile

#include <bits/stdc++.h>
using namespace std;

inline namespace FileIO {
void setIn(string s) { (void)!freopen(s.c_str(), "r", stdin); }
void setOut(string s) { (void)!freopen(s.c_str(), "w", stdout); }
void setIO(string s = "") {
  ios::sync_with_stdio(false);
  cin.exceptions(cin.failbit);  // throws exception when do something illegal
  cin.tie(nullptr);             // unsync C / C++ I/O streams
  cout.tie(nullptr);            // unsync C / C++ I/O streams
  if (int(s.size())) setIn(s + ".in"), setOut(s + ".out");  // for old USACO
}
}  // namespace FileIO

#define endl "\n"
// #define all(x) (x).begin(), (x).end()
// #define rall(x) (x).rbegin(), (x).rend()
using ll = long long;
// using ul = unsigned long long;
using sz = size_t;

template <typename... Ts>
using V = vector<Ts...>;
template <typename T1, typename T2>
using P = pair<T1, T2>;
// template <typename T, sz N> using A = array<T, N>;
// template <typename... Ts> using D = deque<Ts...>;
// template <typename... Ts> using T = tuple<Ts...>;
// template <typename... Ts> using uS = unordered_set<Ts...>;
// template <typename... Ts> using S = set<Ts...>;
// template <typename... Ts> using uM = unordered_map<Ts...>;
// template <typename... Ts> using M = map<Ts...>;
// template <typename... Ts> using umM = unordered_multimap<Ts...>;
// template <typename... Ts> using mM = multimap<Ts...>;
// template <typename... Ts> using pQ = priority_queue<Ts...>;

class Solution {
 public:
  auto Solve(sz n, sz len, V<P<ll, ll>> &p) {
    auto fn = [&](double mid) {
      double curr = 0;
      for (int i = 0; i < n; i++) {
        double delta = sqrt(mid * mid - p[i].second * p[i].second);
        double a = p[i].first - delta, b = p[i].first + delta;
        if (a <= curr) curr = max(curr, b);
      }
      return curr >= len;
    };

    double l = 1, r = 1.5e9;
    while (r - l > 1e-3) {
      double mid = (l + r) / 2, curr = 0;
      if (fn(mid))
        r = mid;
      else
        l = mid;
    }
    return l;
  }
};

int main() {
  setIO();

  Solution solve;
  sz __ = 1ul;
  for (auto _ = 0ul; _ < __; ++_) {
    // input
    sz n, l;
    cin >> n >> l;
    V<P<ll, ll>> p(n);
    for (auto &pp : p) cin >> pp.first >> pp.second;

    // solve
    auto ans = solve.Solve(n, l, p);

    // output
    cout << fixed << setprecision(4) << ans << endl;
  }
}

• 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