[백준 1004] 어린 왕자 (C#, C++) - soo:bak

문제 링크

1004번 - 어린 왕자

설명

행성계는 서로 겹치지 않는 원으로 주어집니다. 시작점과 도착점이 원 내부인지 외부인지에 따라 해당 원의 경계를 지나야 하는 경우에만 진입 또는 이탈이 1회 발생합니다.

즉, 한 점은 원 안에 있고 다른 점은 원 밖에 있으면 그 원을 한 번 지나야 합니다. 모든 원에 대해 이를 세어 합한 값이 최소 진입·이탈 횟수입니다.

접근법

먼저, 각 원에 대해 시작점까지의 거리 제곱과 도착점까지의 거리 제곱을 계산합니다.

다음으로, 반지름 제곱과 비교해 각 점이 원 안에 있는지 확인합니다.

이후, 두 결과가 다르면 하나는 안에, 하나는 밖에 있으므로 답을 1 증가시킵니다. 원들이 겹치지 않으므로 중첩 이동은 고려하지 않아도 됩니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var T = int.Parse(Console.ReadLine()!);
      for (var tc = 0; tc < T; tc++) {
        var sLine = Console.ReadLine()!.Split();
        var sx = int.Parse(sLine[0]);
        var sy = int.Parse(sLine[1]);
        var ex = int.Parse(sLine[2]);
        var ey = int.Parse(sLine[3]);

        var n = int.Parse(Console.ReadLine()!);
        var ans = 0;
        for (var i = 0; i < n; i++) {
          var c = Console.ReadLine()!.Split();
          var cx = int.Parse(c[0]);
          var cy = int.Parse(c[1]);
          var r = int.Parse(c[2]);
          var r2 = r * r;

          var ds = (cx - sx) * (cx - sx) + (cy - sy) * (cy - sy);
          var de = (cx - ex) * (cx - ex) + (cy - ey) * (cy - ey);

          var inS = ds < r2;
          var inE = de < r2;
          if (inS != inE)
            ans++;
        }
        Console.WriteLine(ans);
      }
    }
  }
}

C++

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

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

  int T; cin >> T;
  while (T--) {
    int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey;
    int n; cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) {
      int cx, cy, r; cin >> cx >> cy >> r;
      int r2 = r * r;
      int ds = (cx - sx) * (cx - sx) + (cy - sy) * (cy - sy);
      int de = (cx - ex) * (cx - ex) + (cy - ey) * (cy - ey);
      bool inS = ds < r2;
      bool inE = de < r2;
      if (inS != inE)
        ans++;
    }
    cout << ans << "\n";
  }

  return 0;
}