기하학 - 1002

백준 온라인 코딩 문제풀이

https://www.acmicpc.net/

Baekjoon Online Judge

---

기하학 1002번 터렛 문제

좌표 (x1, y1), (x2, y2)와 한 점까지의 거리를 각각 r1, r2로 주어졌을 때 몇개의 점이 겹치는지를 구하는 문제다.

 

우선 다음과 같이 접근해보았다

결국 좌표 두 개에서 거리가 주어졌을 때 있을 수 있는 좌표는 두 원의 교점으로 볼 수 있다.

 

따라서 경우의 수는

1. 원이 완벽하게 겹칠 때

2. 두 점에서 교점이 있을 때

3. 한 점에서 교점이 있을 때

4. 교점이 없을 때

이렇게 4가지 경우의 수가 있다.

 

그리고 교점의 좌표를 구할 이유가 없기 때문에 브루트포스 방식으로 제한에 있는 모든 좌표를 분석할 이유가 없다.

 

아래는 구현을 해보겠다

using System;
using System.Linq;
using System.Collections.Generic;
namespace StudyCS
{
    class Program
    {
        public static void Main(string[] args)
        {
            int testCase = int.Parse(Console.ReadLine());
            List<List<int>> input = new List<List<int>>();
            int[] output = new int[testCase];
            // input = {x1, y1, r1, x2, y2, r2}
            // calculate distance = (x1-x)^2 + (y1-y)^2 = r1^2 && (x2-x)^2 + (y2-y)^2 = r2^2
            for (int i = 0; i < testCase; i++)
            {
                input.Add(Array.ConvertAll(Console.ReadLine().Split(), int.Parse).ToList());
                output[i] = CaculateCircle(input[i]);
            }
            for (int i = 0; i < testCase; i++)
            {
                Console.WriteLine(output[i]);
            }
        }
        public static int CaculateCircle(List<int> _input)
        {
            int _x1 = _input[0];
            int _y1 = _input[1];
            int _r1 = _input[2];
            int _x2 = _input[3];
            int _y2 = _input[4];
            int _r2 = _input[5];
            double circle = Math.Sqrt(Math.Pow(_x1 - _x2, 2) + Math.Pow(_y1 - _y2, 2));
            // 원이 완전히 겹치는 경우
            if (_x1 == _x2 && _y1 == _y2 && _r1 == _r2)
            {
                return -1;
            }
            // 교점이 없는 경우
            else if (circle < Math.Abs(_r1 - _r2) || circle > _r1 + _r2)
            {
                return 0;
            }
            // 교점이 존재하는 경우
            // 교점이 하나인 경우
            else if(circle ==  Math.Abs(_r2 - _r1) || circle == Math.Abs(_r2 + _r1))
            {
                return 1;
            }
            // 교점이 두개인 경우
            else
            {
                return 2;
            }
        }
    }
}