본문 바로가기

매일 알고리즘 2문제

1002 터렛

정답률이 굉장히 낮음에도 불구하고, 고등학교 때 ' 두 원의 교점 구하기' 문제를 풀어봤던 사람이라면

풀 수 있는 문제이다.


참고로 문제를 보고, 바로 원을 떠올릴 수 있어야 하고 필자의 경우 고등학생 시절 풀었던 SSEN 을 참고하여 구현해보았다.


규칙을 아래와 같이 5개의 규칙으로 나누어질 수 있는데

 

1. 한 원 안에 다른 원이 포함되 있는 경우

    => 이 경우 내접하는지, 내접한다면 두원사이의 반지름길이가 같은지에 따라 세부적으로 나누어질 수 있다.


2. 두 원이 포함관계는 성립하지 않지만, 2개의 교점이 있는 경우


3. 두 원이 포함관계는 성립하지 않지만, 1개의 교점이 있는 경우


4. 포함관계도 성립하지 않고, 교점 또한 없는 경우



어떻게보면 5가지로 나누어질 수 있으나, 그림을 통해 설명해보겠다.


 INPUT (X1,Y1,R1,X2,Y2,R2)



1번 경우 포함되어 있음



1번의 세부항목 -> 내접하면서 반지름의 길이가 다름



1번의 세부항목 -> 내접하면서 반지름 길이가 같음



2번



3번



4번



정리안된 소스코드이지만, 아래 올려두었다. 


                        출처 ) SSEN 문제집! (오랜만이다 쎈! :) )


<소스코드> (참고로 <cmath> 헤더의 sqrt를 사용할 수 있다!)



#include <cstdio>

int x1, y1, r1, x2, y2, r2,T;

int main() {
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d%d%d%d%d%d", &x1, &y1, &r1, &x2, &y2, &r2);
		long long distance = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1);
		long long r_minus = (r2 - r1)*(r2 - r1);
		long long r_plus = (r2 + r1)*(r2 + r1);
		if (distance < r_minus) printf("0\n");
		else if (distance == r_minus) {
			if (r1 == r2) printf("-1\n");
			else printf("1\n");
		}
		else if (r_minus < distance && distance < r_plus) printf("2\n");
		else if (r_plus == distance) printf("1\n");
		else if (distance > r_plus) printf("0\n");
	}
	return 0;
}


'매일 알고리즘 2문제' 카테고리의 다른 글

2293 동전1  (0) 2018.02.20
10431 줄세우기  (0) 2018.02.13
10426 기념일2  (0) 2018.02.07
3231 카드놀이  (0) 2018.02.07
4153 직각삼각형  (0) 2018.02.06