[백준알고리즘] 3053번: 택시 기하학 -Python, C++

[백준알고리즘] 3053번: 택시 기하학 -Python, C++

3053번: 택시 기하학 (acmicpc.net)

3053번: 택시 기하학

유클리드 거리(Euclidean distance)와 택시 거리(맨하탄 거리, Manhattan distance)에 대한 내용을 다루고 있다.

 

유클리드 거리는 어릴 때 배우는 피타고라스 정리에 의한 거리 계산 방법이다.

두 점 \((x_1, x_2)\)와 \((y_1, y_2)\) 사이의 거리는 \(\sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2}\)이다.

 

반면 맨해튼 거리는 두 점 사이의 거리를 유클리드 거리 방식과 다르게 구한다.

두 점 \((x_1, x_2)\)와 \((y_1, y_2)\) 사이의 거리는 \(|x_1-y_1| + |x_2-y_2|\)이다.

 

아래는 유명한 그림으로 위키피디아에 있는 걸 가져왔다.

유클리드 거리와 맨하탄 거리

가장 왼쪽 아래에 있는 점에서 오른쪽 위의 점 사이의 거리를 구하려고 할 때 유클리드 거리는 가운데 녹색 선과 일치한다.

그리고 정의에 따른 맨해튼 거리는 빨간색 선과 일치할 것이다.

 

하지만 잘 살펴보면 빨간색, 파란색, 노란색 선은 모두 길이가 같다는 것을 알 수 있다. 이것이 맨하탄 거리의 특징이다.

 

아무튼 이 문제는 예전에 파이썬으로도 풀었는데 파이썬으로는 너무 쉽게 풀려서 그런가 포스팅을 안 했었다. 그래서 지금 쓰는 김에 써보려고 한다. 파이썬 코드는 C++ 코드 아래에 적어두었다.

 

---

 

C++로 푸는 데 있어서 PI 상수가 어디에 위치해있는지 찾아야 했다. 방법은 다양하게 있었다.

1. #define _USE_MATH_DEFINES 선언 후 <math.h> 헤더의 M_PI 상수를 이용
2. <cmath>의 acos를 사용해서 acos(-1)을 통해 PI 상수 생성
3. <cmath>의 atan을 사용해서 atan(1) * 4로 PI 상수 생성
4. boost::math::constants::pi를 사용
5. <numbers>의 pi 상수 이용 

 

위의 방법 중 4번을 제외하고 시도해보았다.

1번 방법인 <math.h> 헤더의 M_PI를 시도해보았는데, 이상하게 <cmath>로는 동작을 하지 않았다. 흠..

 

근데 C++을 하면서 굳이 C언어 형태의 <math.h> 헤더를 사용하고 싶지는 않아서 acos를 사용해서 문제를 해결했다.

 

5번 방법의 경우에는 C++ 20에 새로 추가되었다고 한다. <numbers> 헤더를 포함시키고 std::numbers::pi를 사용하면 된다.

 

출력 단위도 고려해줘야 한다. 입력되는 반지름이 10000 이하의 자연수이지만 1/1000의 정확도를 가지며 소수점 6번째 자리까지 출력을 하기 때문에 float을 사용하면 틀렸다고 뜬다.

 

따라서 double을 사용해주고 std::fixed와 std::precision을 사용했다.

fixed의 경우에는 부동소수점 방식의 실수형을 고정소수점으로 만드는 것이다. 보통의 실수형은 더 큰 수를 표현할 수 있는 부동소수점 방식을 취하는데, 여기서 fixed를 사용해주는 것은 precision을 통해 소수점 아래 자릿수를 고정시키기 위함이다.

precision 같은 경우에는 원래 정수부와 소수부를 합친 모든 숫자의 최대 개수를 의미한다. 하지만 fixed가 cout에 설정되어 있다면 precision은 소수점 아래의 정확도를 의미하게 된다. 따라서 소수점 정확도보다 낮은 값이 들어오면 반올림으로 소수점 아래 자리수를 맞춰주며 정확도보다 큰 값이 들어오면 \(0 padding\)을 해준다.

 

#include <iostream>
#include <cmath>

#define PI acos(-1) // atan(1) * 4

void solve(void);

int main(void)
{
	solve();
}

void solve(void)
{
	double r;
	std::cin >> r;

	std::cout << std::fixed;
	std::cout.precision(6);
	std::cout << r * r * PI << std::endl;
	std::cout << r * r * 2 << std::endl;
}

 

아래는 파이썬 코드다.

from math import pi
r = int(input())
print("{:.6f}".format(pi * (r ** 2)))
print("{:.6f}".format(2 * (r ** 2)))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

참고 : 맨해튼 거리 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)