Submission #1359548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359548		kstaniszewski351	Mobile (BOI12_mobile)	C++20	0 / 100	1097 ms	40364 KiB

mobile

#include <bits/stdc++.h>
#include <iomanip>
#include <limits>
#include <vector>


//intersection with y = 0
std::optional<std::pair<double, double>> circle_eq(int a, int b, double r) {
  double delta = 4.0*r*r - 4.0*b*b;
  if(delta < 0) {
    return {};
  }

  double delta_r = std::sqrt(delta);


  double x1 = ((2.0*a) - delta_r) / 2.0;
  double x2 = ((2.0*a) + delta_r) / 2.0;
  return {{x1, x2}};
}

bool verify(std::vector<std::pair<int, int>>& circles, int L,  double r) {
  std::vector<std::pair<double, double>> ranges;
  for(auto& c : circles) {
    auto sol = circle_eq(c.first, c.second, r);
    if(!sol.has_value() || sol->first == sol->second) {
      continue;
    }
    std::pair<double, double> r = {std::min(sol->first, sol->second), std::max(sol->first, sol->second)};

    if(r.second >= 0 && r.second <= L) {
      if(r.first >= 0) {
        ranges.push_back(r);
      }
      else {
        ranges.push_back({0, r.second});
      }
    }
    else if(r.second > L) {
      if(r.first <= L && r.first >= 0) {
        ranges.push_back({r.first, L});
      }
      else if(r.first < 0) {
        ranges.push_back({0, L});
      }
    }
  }
  if(ranges.size() == 0) {
    return false;
  }

  std::sort(ranges.begin(), ranges.end(), [](auto& a, auto& b) {return a.first < b.first;});

  //double begin = ranges[0].first;
  if(ranges[0].first != 0) {
    return false;
  }
  double end = ranges[0].second;

  for(int i = 1; i < ranges.size(); i++) {
    auto& r = ranges[i];

    if(r.first <= end) {
      end = r.second;
    }
    else {
      return false;
    }
  }
  
  if(end >= L) {
    return true;
  }

}

int main() {
  int n, L;
  std::cin >> n >> L;
  std::vector<std::pair<int, int>> circles(n);
  
  for(auto& c : circles) {
    std::cin >> c.first;
    std::cin >> c.second;
  }

  // double r;
  // std::cin >> r;
  // std::cout << verify(circles, L, r);

  double l = 0;
  double r = std::numeric_limits<float>::max();

  while(r - l > 10e-4) {
    double mid = (l+r) / 2;

    if(verify(circles, L, mid)) {
      r = mid;
    }
    else {
      l = mid;
    }
  }

  std::cout << std::setprecision(5) << (r+l) /2;
}

Compilation message (stderr)

mobile.cpp: In function 'bool verify(std::vector<std::pair<int, int> >&, int, double)':
mobile.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
   75 | }
      | ^

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