[C]백준_17093 : Total Circle

Alal11·2023년 3월 9일

C boj

출처

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

문제

좌표평면상의 점의 배열 P = P1, P2, ⋯, PN와 Q = Q1, Q2, ⋯, QM이 있다. Q 배열 상의 한 점을 중심으로, P 배열 상의 모든 점을 포함하는 최소 넓이의 원의 반지름 중 최댓값을 구하시오.

입력

첫 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 1000)

N개의 줄에 걸쳐 x와 y가 주어지며, 이는 Pi = (x,y)라는 뜻이다. (-106 ≤ x,y ≤ 106)

M개의 줄에 걸쳐 x와 y가 주어지며, 이는 Qi = (x,y)라는 뜻이다. (-106 ≤ x,y ≤ 106)

출력

Q 배열 상의 한 점을 중심으로, P 배열 상 모든 점을 포함하는 최소 넓이의 원의 반지름 중 최댓값의 제곱을 출력한다.

예제 입출력

알고리즘 분류

브루트포스 알고리즘
기하학
피타고라스 정리

➡️문제 분석

원의 방정식 공식, 점과 점 사이 거리 공식을 이용하여
원의 정점을 (a, b), 반지름을 r, 원을 지나는 임의의 점을 (x, y)라고 할 때
(x-a)제곱 + (y-b)제곱 = r제곱 이라는 식이 성립한다.

위 식을 이용하여 문제를 풀어보자!

➡️코드(⭕)

#include <stdio.h>
#include <math.h>

long long int radius(int p_x, int p_y, int q_x, int q_y)
{
	return pow((p_x - q_x), 2) + pow((p_y - q_y), 2);
}

int main(void) {

	int p[2000], q[2000];
	int p_cnt, q_cnt;
	long long int answer = 0;
	long long int radius_cal;

	scanf("%d %d", &p_cnt, &q_cnt);

	for (int i = 0; i < p_cnt * 2; i += 2)
		scanf("%d %d", &p[i], &p[i + 1]);

	for (int i = 0; i < q_cnt * 2; i += 2)
		scanf("%d %d", &q[i], &q[i + 1]);

	for (int i = 0; i < p_cnt * 2; i += 2) {
		for (int j = 0; j < q_cnt * 2; j += 2) {
			radius_cal = radius(p[i], p[i + 1], q[j], q[j + 1]);
			answer = answer > radius_cal ? answer : radius_cal;
		}
	}
	printf("%lld\n", answer);

	return 0;
}

➡️코드 분석

사용자 정의 함수 radius()를 선언하여 두 점의 x, y 좌표값을 매개변수로 받고, 거듭제곱 함수 pow()로 문제 분석에서 말한 (x-a)제곱 + (y-b)제곱을 구현해준다.
점 p와 점 q의 개수를 입력받고, 그 개수 만큼의 x값과 y값을 각각 입력받아서 p와 q 배열에 넣어준다.
사용자 정의 함수 radius()를 호출하여 p와 q의 각각 x, y 좌표를 매개변수로 넘겨주고, 구한 값인 r제곱을 radius_cal에 넣어준다.
원의 반지름 제곱의 최댓값을 출력하기 위해 삼항연산자로 radius_cal의 최댓값을 구해주고 출력한다.