백준 1004번: 어린 왕자

백준 온라인 저지(BOJ) 1004번 문제

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

1. 문제 요약

여러 원에 둘러쌓인 두 점이 있다. 한 점에서 다른 한 점으로 갈 때,

지나야 하는 경계의 최소 개수는?

(원의 경계가 맞닿거나 교차하는 경우는 없다)

2. 알고리즘

원의 경계가 맞닿거나 교차하는 경우는 없다는 조건 때문에 문제풀이가 쉬워진다.

두 점이

i) 둘 다 원 안에 있다면 0번

ii) 둘 다 원 밖에 있다면 0번

iii) 둘 중 하나만 원 안에 있다면 1번

씩 더해주면 된다.

1002번과 마찬가지로 거리를 비교할 때 sqrt를 쓰지 않는 편이 이롭다.

3. 코드

#include <iostream>

int main() {
	int T;
	scanf("%d", &T);

	for (int i = 0; i < T; ++i) {
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

		int n;
		scanf("%d", &n);
		int count = 0;
		for (int j = 0; j < n; ++j) {
			int cx, cy, r, d;
			bool in1, in2;

			scanf("%d %d %d", &cx, &cy, &r);
			d = (cx - x1) * (cx - x1) + (cy - y1) * (cy - y1);
			in1 = d > r * r ? false : true;
			d = (cx - x2) * (cx - x2) + (cy - y2) * (cy - y2);
			in2 = d > r * r ? false : true;
			if (in1 != in2) count++;
		}
		printf("%d\n", count);
	}

	return 0;
}