[백준 9611] Vicinity (C#, C++) - soo:bak

문제 링크

9611번 - Vicinity

설명

평면상의 n개 점이 주어지고, 여러 쿼리마다 기준점 pi와 거리 dv가 주어집니다. 기준점을 제외한 다른 점들 중 거리 ≤ dv 인 점의 개수를 세어 출력합니다.

접근법

각 쿼리에서 모든 점과의 거리 제곱을 계산해 거리 제곱 이하인지 확인합니다. 실수 오차를 피하기 위해 제곱으로 비교합니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Text;

class Program {
  static void Main() {
    var parts = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
    var idx = 0;
    var n = int.Parse(parts[idx++]);

    var xs = new int[n];
    var ys = new int[n];
    for (var i = 0; i < n; i++) {
      xs[i] = int.Parse(parts[idx++]);
      ys[i] = int.Parse(parts[idx++]);
    }

    var t = int.Parse(parts[idx++]);
    var sb = new StringBuilder();
    for (var q = 0; q < t; q++) {
      var id = int.Parse(parts[idx++]) - 1;
      var dv = int.Parse(parts[idx++]);
      var dv2 = dv * dv;

      var cnt = 0;
      for (var j = 0; j < n; j++) {
        if (j == id)
          continue;
        var dx = xs[j] - xs[id];
        var dy = ys[j] - ys[id];
        var dist2 = dx * dx + dy * dy;
        if (dist2 <= dv2)
          cnt++;
      }
      sb.AppendLine(cnt.ToString());
    }

    Console.Write(sb);
  }
}

C++

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

typedef long long ll;
typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi x(n), y(n);
  for (int i = 0; i < n; i++)
    cin >> x[i] >> y[i];

  int t; cin >> t;
  while (t--) {
    int id, dv; cin >> id >> dv;
    id--;
    ll dv2 = 1LL * dv * dv;
    int cnt = 0;
    for (int j = 0; j < n; j++) {
      if (j == id)
        continue;
      ll dx = x[j] - x[id];
      ll dy = y[j] - y[id];
      ll dist2 = dx * dx + dy * dy;
      if (dist2 <= dv2)
        cnt++;
    }
    cout << cnt << "\n";
  }

  return 0;
}