Submission #1263333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263333		rtri	Park (BOI16_park)	C++20	0 / 100	2595 ms	2188 KiB

park

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

int n, m, w, h;
vector<tuple<int, int, int>> trees;

bool line_of_sight(double x1, double y1, double x2, double y2, int radius) {
  for (auto [x, y, base_r] : trees) {
    int r = base_r + radius;
    double u = (double)((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) /
               (double)((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
    double ex = x1 + clamp(u, 0., 1.) * (x2 - x1);
    double ey = y1 + clamp(u, 0., 1.) * (y2 - y1);
    double dist = sqrt((ex - x) * (ex - x) + (ey - y) * (ey - y));
    if (dist < r)
      return false;
  }
  return true;
}

pair<double, double> get_exit(int exit_id, int radius) {
  if (exit_id == 1)
    return {radius, radius};
  else if (exit_id == 2)
    return {w - radius, radius};
  else if (exit_id == 3)
    return {w - radius, h - radius};
  else if (exit_id == 4)
    return {radius, h - radius};
  else
    exit(-1);
}

bool pathfind(int start, int end, int radius) {
  auto [startx, starty] = get_exit(start, radius);
  auto [endx, endy] = get_exit(end, radius);

  deque<tuple<double, double, int>> que;
  que.push_back({startx, starty, 0});
  while (!que.empty()) {
    auto [x, y, r] = que.front();
    que.pop_front();

    cerr << x << " " << y << " " << que.size() << endl;
    if (line_of_sight(x, y, endx, endy, radius))
      return true;

    for (auto [treex, treey, base_r] : trees) {
      int treer = base_r + radius;

      double d = sqrt(pow(x - treex, 2) + pow(y - treey, 2));
      double alpha = atan2(y - treey, x - treex);
      double alpha_inv = atan2(treey - y, treex - x);

      vector<tuple<double, double, double, double>> cand = {};

      if (d >= r + treer) {
        double int_theta = acos((r + treer) / d);
        cand.push_back({cos(int_theta + alpha_inv), sin(int_theta + alpha_inv),
                        cos(int_theta - alpha), sin(int_theta - alpha)});
        cand.push_back({cos(int_theta - alpha_inv), sin(int_theta - alpha_inv),
                        cos(int_theta + alpha), sin(int_theta + alpha)});

        double ext_theta = acos(abs(r - treer) / d);
        cand.push_back({cos(ext_theta + alpha_inv), sin(ext_theta + alpha_inv),
                        cos(ext_theta - (M_PI + alpha)),
                        sin(ext_theta - (M_PI + alpha))});
        cand.push_back({cos(ext_theta - alpha_inv), sin(ext_theta - alpha_inv),
                        cos(ext_theta - (M_PI - alpha)),
                        sin(ext_theta - (M_PI - alpha))});
      }

      for (auto [cx, cy, nx, ny] : cand) {
        // TODO requires checking if sphere intersects or we are allowed to
        // slide
        // cx = cx * r + x, cy = cy * r + y;
        nx = nx * treer + treex, ny = ny * treer + treey;

        if (line_of_sight(x, y, nx, ny, radius))
          que.push_back({nx, ny, treer});
      }
    }
  }

  return false;
}

int main() {
  feenableexcept(FE_DIVBYZERO | FE_INVALID | FE_OVERFLOW);

  cin >> n >> m >> w >> h;

  for (int i = 0; i < n; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    trees.push_back({x, y, r});
  }

  vector<pair<int, int>> queries;

  for (int i = 0; i < m; i++) {
    int r, e;
    cin >> r >> e;
    queries.push_back({e, r});
  }

  // Insikt 1: det finns bara 6 möjliga vägar (4 välj 2)
  // Insikt 2: vi kan binärsöka över varje vägbredd (ca. log 1e9 \approx 30)

  vector<vector<int>> max_width(5, vector<int>(5, -1));

  for (int start = 1; start <= 4; start++)
    for (int end = start; end <= 4; end++) {
      if (start == end) {
        max_width[start][end] = 1e9;
        max_width[end][start] = 1e9;
        continue;
      }

      int l = 0, r = min(w, h) / 4 + 3;
      while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (pathfind(start, end, mid))
          l = mid;
        else
          r = mid;
      }
      max_width[start][end] = l;
      max_width[end][start] = r;
    }

  for (auto [e, r] : queries) {
    for (int exit = 1; exit <= 4; exit++)
      if (r <= max_width[e][exit])
        cout << exit;
    cout << "\n";
  }

  return 0;
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42