Submission #1046838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046838		JohnnyVenturas	Mobile (BOI12_mobile)	C++17	8 / 100	460 ms	8016 KiB

mobile

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;

pair<int, int> receivers[MAXN];

int last_true(int low, int high, function<bool(double)> f) {
  --low;

  for (int diff = high - low; diff > 0; diff /= 2) {
    while (low + diff <= high && f(low + diff))
      low += diff;
  }

  return low;
}

double first_true(double low, double high, function<bool(double)> f) {
  --low, ++high;

  double mid;

  while (high - low > 1e-5) {
    mid = low + (high - low) / 2;
    if (f(mid)) {
      high = mid;
    } else {
      low = mid;
    }
  }

  return high;
}

bool intersect(pair<int, int> &center, double r, double L, double &left,
               double &right) {
  const auto &[x, y] = center;

  double c = y;
  double y0 = -c;
  double d0 = abs(c);

  left = -1 / 0., right = -1 / 0.;

  if (d0 > r)
    return false;

  double d = sqrt(r * r - d0 * d0);

  double m = d;

  double ax = m, ay = y0;
  double bx = -m, by = y0;

  left = ax + x;
  right = bx + x;
  if(left > right) swap(left, right);

  return true;
}

int main() {
  int N, L;
  cin >> N >> L;

  for (int i = 0; i < N; ++i) {
    cin >> receivers[i].first >> receivers[i].second;
  }


  cout << first_true(0.0001, 2e9, [&](double r) {
	 double last_right = 0.0;
    for (int i = 0; i < N; ++i) {
      double left, right;
      bool did_intersect = intersect(receivers[i], r, L, left, right);

	  if(!did_intersect) continue;

	  if(right < 0) continue;

	  if(left > last_right) continue;

	  last_right = max(last_right, right);
    }

	return last_right >= L;

  }) << "\n";
}

Compilation message (stderr)

mobile.cpp: In function 'bool intersect(std::pair<int, int>&, double, double, double&, double&)':
mobile.cpp:54:18: warning: unused variable 'ay' [-Wunused-variable]
   54 |   double ax = m, ay = y0;
      |                  ^~
mobile.cpp:55:19: warning: unused variable 'by' [-Wunused-variable]
   55 |   double bx = -m, by = y0;
      |                   ^~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 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