[G4] 백준 5631번 방사능 C++ 정렬, 기하학, 이분 탐색

리뷰

 

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

두 원의 내접에 존재하지 않는 집의 수를 구하는 문제, 교집합은 2배로 처리해 준다.

 

 

전역 변수

• n : 집의 개수를 저장할 변수
• Pos : 집의 위치 x, y좌표를 정의할 구조체
• lst : 집의 위치들을 저장할 Pos타입 배열
• adists, bdists : a, b원자력 발전소로 부터 모든 집 까지의 거리를 저장할 배열

 

함수

1. getDist

double getDist(int x, int y, int tx, int ty)

 

원자력 발전소와 집의 거리를 구하는 함수

1. 매개 변수로 집의 좌표 x, y와 원자력 발전소의 좌표 tx, ty를 전달 받는다.
2. ((x - tx)^2 + (y - ty)^2)^1/2를 계산하여 리턴해 준다.

 

문제풀이

1. 변수 c를 0으로 초기화 한다. 해당 변수는 테스트 케이스의 개수를 의미한다.
2. c를 전위 증가시키고 무한히 동작하는 while 루프를 수행해 준다.
3. 매 루프마다 n값을 입력 받고, 만약 n이 0이라면 break 처리해 준다.
4. Case에 해당하는 내용을 상수 문자열과 변수 c를 활용해 출력해 준다.
5. n개의 집 좌표 정보를 lst배열에 입력 받아준다.
6. 두 발전소의 위치와 쿼리문의 개수를 입력 받아준다.
7. n개의 집을 순회하며 각 집과 a, b발전소의 거리를 getDist함수로 구해 adists, bdists 배열에 각각 저장해 준다.
8. sort함수를 통해 adists, bdists 배열의 값을 오름차순으로 정렬해 준다.
9. q개의 쿼리문을 실행해 각 쿼리마다 발전소 a, b의 반지름 r1, r2를 입력 받아준다.
10. upper_bound를 통해 변수 ac, bc에 거리가 r1, r2이하인 집의 개수를 구해 각각 저장해 준다.
11. ac +bc가 n이상일 경우 0을, 아닐 경우 n에서 ac + bc를 뺀 값을 출력해 준다.

 

트러블 슈팅

1. 복사 붙여넣기를 하다가 ac, bc를 구할 때 모두 반지름을 r1을 사용해 Fail을 받았다.
2. ac는 r1을, bc는 r2을 기준으로 찾도록 로직을 수정하여 AC를 받았다.

 

참고 사항

• 교집합을 따로 구할 필요는 없고 그냥 내접에 있는 집의 개수만 세어주면 된다.
• 거리가 같은 경우도 포함하므로 lower_bound가 아닌 upper_bound를 사용해 주어야 한다.

 

정답 코드

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int N = 200000;
int n;
struct Pos {
	int x, y;
};
Pos lst[N];
double adists[N], bdists[N];

double getDist(int x, int y, int tx, int ty) {
	return pow(pow(x - tx, 2) + pow(y - ty, 2), 0.5f);
}

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

	int c = 0;
	while (++c) {
		cin >> n;
		if (!n) break;
		cout << "Case " << c << ":\n";

		for (int i = 0; i < n; ++i) {
			int x, y; cin >> x >> y;
			lst[i] = { x, y };
		}

		int ax, ay, bx, by, q; cin >> ax >> ay >> bx >> by >> q;
		for (int i = 0; i < n; ++i) {
			adists[i] = getDist(lst[i].x, lst[i].y, ax, ay);
			bdists[i] = getDist(lst[i].x, lst[i].y, bx, by);
		}
		
		sort(adists, adists + n);
		sort(bdists, bdists + n);
		while (q--) {
			int r1, r2; cin >> r1 >> r2;
			int ac = upper_bound(adists, adists + n, r1) - adists;
			int bc = upper_bound(bdists, bdists + n, r2) - bdists;
			int result = ac + bc >= n ? 0 : n - (ac + bc);
			cout << result << "\n";
		}
	}
}