BOJ 13552 - 구와 쿼리

문제

N개의 3차원 좌표와 Q개의 구가 주어질 때, 각 구 내부에 포함된 점의 개수를 구하라.

입력

점의 개수 N과 각 좌표, 쿼리 수 Q와 각 구의 중심 좌표 및 반지름이 주어진다.

출력

각 쿼리마다 구 내부에 포함된 점의 개수를 출력한다.

예제

입력	출력
`3` `0 0 0` `1 1 1` `2 2 2` `1` `0 0 0 2`	`2`

풀이

각 쿼리마다 모든 점과의 거리를 계산하여 구 내부 여부를 판별한다.

N개의 3차원 좌표를 배열에 저장한다
각 쿼리마다 모든 점에 대해 중심과의 유클리드 거리의 제곱을 구한다
거리 제곱이 반지름 제곱 이하인 점의 개수를 센다

핵심 아이디어: 제곱근 연산 없이 제곱 상태로 비교하면 부동소수점 오차를 피할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;
 
const int N = 300005, INF = 1000000000;
array<int, 3> vs[N];
int n, q;
int main()
{
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> vs[i][0] >> vs[i][1] >> vs[i][2];
  }
  cin >> q;
  while (q--)
  {
    long long x, y, z;
    long long r;
    cin >> x >> y >> z >> r;
    r = r * r;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
      auto [X, Y, Z] = vs[i];
      long long d = (x - X) * (x - X) + (y - Y) * (y - Y) + (z - Z) * (z - Z);
      if (d <= r)
        ans++;
    }
    cout << ans << "\n";
  }
}

복잡도

시간: O(N × Q)
공간: O(N)

문제