Submission #1131201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131201		TraianDanciu	Circle selection (APIO18_circle_selection)	C++20	100 / 100	2036 ms	55236 KiB

circle_selection

#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
#include <set>

const int MAXN = 300'000;
const int INFINIT = 2'000'000'000;

int n, answer[MAXN], region_size;

struct Circle {
  int x, y, r, idx;
} circles[MAXN];

std::map<std::pair<int, int>, std::vector<int>> regions;
std::set<int> active;

void readCircles() {
  int i;
  scanf("%d", &n);
  for(i = 0; i < n; i++) {
    scanf("%d%d%d", &circles[i].x, &circles[i].y, &circles[i].r);
    circles[i].idx = i;
    active.insert(i);
  }
}

void sortCircles() {
  std::sort(circles, circles + n, [](Circle a, Circle b) {
    if(a.r == b.r) {
      return a.idx < b.idx;
    }
    return a.r > b.r;
  });
}

void buildRegions(int new_size) {
  std::set<int>::iterator it;
  region_size = new_size;
  regions.clear();
  it = active.begin();
  while(it != active.end()) {
    regions[{circles[*it].x / region_size, circles[*it].y / region_size}].push_back(*it);
    it++;
  }
}

long long square(int x) {
  return 1LL * x * x;
}

int circlesTouch(int a, int b) {
  return square(circles[a].r + circles[b].r) >= square(circles[a].x - circles[b].x)
                                              + square(circles[a].y - circles[b].y);
}

void scanCircles() {
  int i, xregion_new, yregion_new, xregion, yregion, j, neighbour;
  region_size = INFINIT;
  for(i = 0; i < n; i++) {
    if(answer[circles[i].idx] == 0) {
      if(2 * circles[i].r <= region_size) {
        buildRegions(circles[i].r);
      }

      xregion = circles[i].x / region_size;
      yregion = circles[i].y / region_size;
      for(xregion_new = xregion - 2; xregion_new <= xregion + 2; xregion_new++) {
        for(yregion_new = yregion - 2; yregion_new <= yregion + 2; yregion_new++) {
          if(regions.count({xregion_new, yregion_new})) {
            for(j = 0; j < (int)regions[{xregion_new, yregion_new}].size(); j++) {
              neighbour = regions[{xregion_new, yregion_new}][j];
              if(answer[circles[neighbour].idx] == 0 && circlesTouch(i, neighbour)) {
                answer[circles[neighbour].idx] = circles[i].idx + 1;
                active.erase(neighbour);
              }
            }
          }
        }
      }
    }
  }
}

void writeAnswer() {
  int i;
  for(i = 0; i < n; i++) {
    printf("%d ", answer[i]);
  }
  fputc('\n', stdout);
}

int main() {
  readCircles();
  sortCircles();
  scanCircles();
  writeAnswer();
  return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'void readCircles()':
circle_selection.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
circle_selection.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d%d%d", &circles[i].x, &circles[i].y, &circles[i].r);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13