Boj 1002 터렛

1. 문제

https://www.acmicpc.net/problem/1002

1002번: 터렛

2. 문제에서 원하는 것

A와 B의 좌표가 주어지고 A와 C, B와 C 사이의 거리가

주어질 때 C가 있을 수 있는 위치의 개수는?

3. 적용할 알고리즘

기하, 두 원의 교점

4. 설명

C와의 거리를 이용하면 C가 있을 수 있는 곳을 원으로 표현 가능 하다.

따라서 두 점으로 부터의 거리를 모두 만족하는

두 원의 교점이 C가 있을 수 있는 점이된다.

그리고 두 점 사이의 거리 dis, r1 + r2와 r1 - r2(r1 > r2일 때)의 값을 이용해

교점이 몇 개 생기는지 알 수 있다.

1) dis > r1 + r2

교점이 생기지 않는다.

 

2) dis == r1 + r2

교점이 하나 생긴다(외접)

 

3) dis < r1 + r2

의 경우는 r1 - r2에 따라 또 세 가지로 나뉜다.

 

3-1) dis > r1 - r2

교점이 두개 생긴다

 

3-2) dis == r1 - r2

교점이 하나 생긴다(내접)

 

3-3) dis < r1 - r2

큰 원 안에 작은 원이 있다, 교점이 없다

 

예외) x1 == x2 && y1 == y2 && r1 == r2

두 원이 완전히 겹친다 => 교점이 무한하다.

 

5. 코드

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<tuple>

using namespace std;

const int INF = 0x7f7f7f7f;

typedef long long ll;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

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

	int t;
	cin >> t;
	while (t--)
	{
		int x1, y1, r1, x2, y2, r2;
		cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;

		int dis = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
		int bigger, smaller;
		if (r1 < r2)
		{
			bigger = r2;
			smaller = r1;
		}
		else
		{
			bigger = r1;
			smaller = r2;
		}

		int sum = bigger + smaller; sum *= sum;
		int sub = bigger - smaller; sub *= sub;

		int ans = 0;

		if (dis > sum)//접하지 않음
			ans = 0;
		else if (dis == sum) //외접한다
			ans = 1;
		else
		{
			if (dis > sub) // 두 점에서 만난다
				ans = 2;
			else if (dis == sub) // 내접한다
				ans = 1;
			else //큰 원 안에 작은 원이 있다
				ans = 0;
		}

		if (r1 == r2 && x1 == x2 && y1 == y2) //똑같다 == 교점이 무한
			ans = -1;

		cout << ans << '\n';
	}
}

6. 느낀 점

이러한 기초적인 수학, 기하학적 논리는 기억해두도록 하자...