[Baekjoon/백준] 1358번: 하키(C/C++)

단계별로 풀어보기 14단계(누적 합) 8번 문제

https://www.acmicpc.net/step/50

기하 1 단계

---

백준 1358번: 하키

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

1358번: 하키

---

문제 설명

지난주에, 민식주식회사는 IIHF(International Ice Hockey Federation)로부터 긴급한 전화를 받았다.

IIHF는 같은 팀이 링크안에 너무 많으면 알람이 울리는 시스템을 설치해달라고 요청했다. 시스템은 다음과 같이 3개의 부분으로 이루어진다.

1. 디지털카메라가 링크의 사진을 매 1초마다 찍는다.
2. 디지털카메라가 찍은 사진에서 각 선수의 위치를 뽑아낸다.
3. 하키 링크 안에 같은 팀 선수가 총 몇 명인지 계산한다.

하키 링크는 (X, Y)가 가장 왼쪽 아래 모서리인 W * H 크기의 직사각형과, 반지름이 H/2이면서 중심이 (X, Y+R), (X+W, Y+R)에 있는 두 개의 원으로 이루어져 있다. 아래 그림을 참고한다.

선수들의 위치가 주어질 때, 링크 안 또는 경계에 있는 선수가 총 몇 명인지 구하는 프로그램을 작성하시오.

---

입력과 출력

입력: 첫째 줄에 수 W H X Y P가 주어진다. P는 선수의 수이다. W와 H는 100보다 작거나 같은 자연수이고, H는 짝수이다. X와 Y는 절댓값이 100보다 작거나 같은 정수이다. P는 최대 50인 자연수이다. 둘째 줄부터 P개의 줄에 각 선수들의 x좌표와 y좌표가 주어진다. 이 좌표는 절댓값이 300보다 작거나 같은 정수이다.

출력: 첫째 줄에 링크 안에 있는 선수의 수를 출력한다.

---

접근 방법

이번 문제는 링크를 2개의 반원과 직사각형으로 나눠봤을 때  직사각형의 폭 W와 높이 H, 왼족 아래 모서리 위치 (X, Y), 선수의 수 P를 입력받고 이후 P개줄에 걸쳐 각 선수의 위치(x, y)를 입력받아서 링크 안에 있는 선수의 수를 출력하는 문제다.

앞서 말했듯 링크를 2개의 반원과 직사각형으로 보면 간단하게 문제를 풀 수 있다. 각 선수의 위치는 직사각형의 왼쪽 모서리 위치 X, Y와 직사각형의 폭 W과 높이 H를 이용해서 해당 값을 구할 수 있다.

우선 왼쪽 반원에 위치한 선수의  두 점 사이의 거리를 구하는 공식을 이용해서 이 값이 반지름보다 작거나 같고, 선수의 x값이 직사각형의 왼쪽 모서리 X값 보다 크지 않으면 된다. 왼쪽 모서리 X 값 보다 크다면 직사각형에 위치하거나 밖에 존재할 수 있기 때문이다. (오른쪽 경계는 후술할 직사각형에서 처리하므로 x와 X가 같으면 안된다)

직사각형은 간단하게 선수의 x, y좌표가 각각 X보다 크거나 같으면서(경계도 된다고 했으므로) X + W보다 같거나 작고, Y도 마찬가지로 Y보다 크거나 같으면서 Y + H보다 같거나 작아야 한다.

오른쪽 반원은 앞의 설명에서 X를 X + W로 변경하기만하면 된다. 조금 지저분한 설명이지만 이렇게 하면 문제를 해결할 수 있다.

---

코드

#include <iostream>
using namespace std;

int main(int argc, char * argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int W, H, X, Y, P, count = 0;

	cin >> W >> H >> X >> Y >> P;

	for (int i = 0; i < P; i++) {
		int x, y;
		cin >> x >> y;

		if (((x - X)*(x - X) + (y - (Y + H/2))*(y - (Y + H/2)) <= (H/2)*(H/2)) && (x < X))
			count++;
		else if ((x >= X) && (x <= X + W) && (y >= Y) && (y <= Y + H))
			count++;
		else if (((x - (X + W))*(x - (X + W)) + (y - (Y + H/2))*(y - (Y + H/2)) <= (H/2)*(H/2))
			&& (X + W < x))
			count++;
	}

	cout << count << endl;

	return 0;
}

---

결과

백준 제출 결과