[백준] 1002 터렛

이 문제를 요약하면 2개의 원이 있고, 그 원이 내접하는지, 외접하는지, 두개의 점에서만나는지, 만나지 않는지를 검사하는 문제이다.

오히려 미사일 터렛의 사진이 문제를 파악하는데 방해가 된다.

잘 읽어보면 류재명이 있을수 있는 좌표란 결국 조규현(이하 x1,y1,r1)과 백승환(이하 x2,y2,r2)의 각 r만큼의 범위는 곧 각각이 원이라는것을 나타내고 이 문제는 두개의 원이 내접/외접/교차/미교차 하는것을 알아내는 문제라는것 알수있다.

즉 이문제는 정답이 -1,0,1,2 이 4가지중에 하나란 얘기가 된다.

 

무수한 점이 있는 경우

우선 정답의 조건중 하나인 류재명이 위치가 무한대로 존재하는 경우란

백승환과 조규현의 x,y,r이 모두 동일한 경우이다.

 

두 반지름의 합과 두 원의 좌표중심간 거리가 같은 경우

그 다음 두 좌표 x1,y1과 x2,y2의 거리(d)와 r1+r2가 동일한 경우가 있다.

식은 (x1-x2)^2 + (y1-y2)^2 == (r1 + r2)^2

이 경우는 원이 외접한 경우라고 생각할수 있다.

이미지 참고 : https://travelerfootprint.tistory.com/61

위의 경우에는 만나는 점이 1개인것을 그림으로 알수있다.

 

두 반지름의 합보다 두 원의 중심좌표간 거리가 더 긴 경우

그 다음은 만나지 않는 경우인데, 위의 그림에서 d가 더 멀어진다고 생각하면 된다.

이 경우  (x1-x2)^2 + (y1-y2)^2 > (r1 + r2)^2로 표현할수 있고 이때 접점은 0개가된다.

 

두 반지름의 합이 두 원의 중심좌표간 거리보다 더 긴 경우

이제 마지막 경우인데 이부분이 조금 처음 풀때 난해했다.

(x1-x2)^2 + (y1-y2)^2 < (r1 + r2)^2 의 케이스인데 그림으로 보면 아래와 같다.

이미지 참고 :https://travelerfootprint.tistory.com/61

두 원의 반지름을 더한것이 두 원의 중심좌표간 거리보다 길어지면 두 원은 두개의 점에서 만난다고 생각하였으나

아래와 같은 경우가 있다.

이미지 참고 :https://travelerfootprint.tistory.com/61

분명 두개 원의 반지름을 더한것이 중심좌표보다 큰데, 내접하는경우와 내접하지 않는 경우로 나눠진다.

코딩시 이부분을 구현해줘야한다.

우선 r1과 r2의 뺀값의 절댓값(이하 offset)을 기준으로 삼아야한다.

이 값이 두 원의 중심거리간 거리(이하 d)보다 긴지, 같은지, 짧은지로 확인이 가능하다.

 

- offset > d

이 경우 두 원이 두개의 점에서 만나는 경우이다.

- offset == d

이 경우 두 원이 내접하여 하나의 점에서 만나는 경우이다.

- offset < d

이 경우 두 원이 내접하지 않는 경우이다.

 

특히 가장 많이 틀렸던 부분은 부동소수점의 문제로 sqrt를 쓰면 오답처리가 되는것이였다.

sqrt를 쓰면 Input을

1

1 3 1 3 2 1 으로 넣으면 출력값이 1로 나온다.

이는 부동소수점의 문제로 정답을 제대로 계산하지 못한것이다.

따라서 sqrt를 쓰지않고 모두다 제곱을 한채로 계산하면 정수계산이 이루어져 정답이 된다. 

 

위의 경우를 모두 따져보면 정답 코드를 만들수있다.

내가 풀었던 코드는 아래 링크에 첨부하였다.

 

https://github.com/manunite/Algorithm/blob/main/acmicpc/Acmicpc/Acmicpc/1002/no_1002.cpp

GitHub - manunite/Algorithm: 개인 알고리즘 문제풀이 한것 저장해놓는 레포지토리