Submission #1046843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046843		JohnnyVenturas	Mobile (BOI12_mobile)	C++17	8 / 100	568 ms	8036 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(long double)> f) {
  --low;

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

  return low;
}

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

  long double mid;

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

  return high;
}

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

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

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

  if (d0 > r)
    return false;

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

  long double m = d;

  long double ax = m, ay = y0;
  long 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, [&](long double r) {
	 long double last_right = 0.0;
    for (int i = 0; i < N; ++i) {
      long double left, right;
      bool did_intersect = intersect(receivers[i], r, L, left, right);

	  if(!did_intersect) continue;

	  if(right + 1e-3 < 0) continue;

	  if(left > last_right + 1e-3) 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>&, long double, long double, long double&, long double&)':
mobile.cpp:54:23: warning: unused variable 'ay' [-Wunused-variable]
   54 |   long double ax = m, ay = y0;
      |                       ^~
mobile.cpp:55:24: warning: unused variable 'by' [-Wunused-variable]
   55 |   long 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