[BOJ-3053][C++] 택시 기하학

문제

19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다.

택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다.

D(T1,T2) = |x1-x2| + |y1-y2|

두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다.

따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다.

원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합

반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 반지름 R이 주어진다. R은 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다.

 

예제 입력 1 

1

 

예제 출력 1 

3.141593
2.000000

 

예제 입력 2 

21

 

예제 출력 2 

1385.442360
882.000000

 

예제 입력 3 

42

 

예제 출력 3 

5541.769441
3528.000000

 

힌트

유클리드 기하학: 한국어 위키 영문 위키 Wolfram Mathworld

비유클리드 기하학: 한국어 위키 영문 위키 Wolfram Mathworld

택시 기하학: 한국어 위키 영문 위키 Wolfram Mathworld

 

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #1 2번

 

알고리즘 분류

• 수학
• 기하학

 

문제 출처

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

3053번: 택시 기하학

 

---

 

문제 해결 방법

• 가볍게 규칙을 발견하여 풀었다.
• 유클리드 기하학에서의 원의 넓이는 $πR^{2}$ 이며, 택시 기하학에서의 원의 넓이는 $2R^{2}$ 이다.

 

코드

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

#define _USE_MATH_DEFINES    // 수학 관련 상수 사용 가능

double R;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> R;

    cout << fixed;
    cout.precision(6);

    cout << M_PI * R * R << '\n' << R * R * 2 << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [기하 1]
• 브론즈III

 

C/C++에서 PI 상수 사용하기

• C/C++에서 PI 상수를 사용하려면 우선 다음의 헤더를 불러와야 한다.

#include <math.h>    // C
#include <cmath>     // C++

 

• 그리고 상단에 다음과 같이 지시자를 적어준다.

#define _USE_MATH_DEFINES    // 수학 관련 상수 사용 가능

 

math.h 헤더의 내부를 보면, 다음과 같이 _USE_MATH_DEFINES 가 명시되어야 수학 관련 상수들을 사용할 수 있다고 명시되어 있다.

 

• 이제 수학 관련 상수들을 사용할 수 있다. PI는 M_PI와 같이 사용하면 된다.

cout << M_PI << endl;

 

택시 기하학(Taxicap Geometry)

개념

• 19세기 수학자인 헤르만 민코프스키(Hermann Minkowski)에 의해 처음 연구되었다.
• 기하학 중에 한가지로, 유클리드 기하학에서의 거리에 대한 정의가 다르다.
• 거리에 대한 내용만 다룰 경우 '맨해튼 거리(Manhattan Distance)', 또는 조금 더 직관적인 이름인 'Rectilinear Distance'라고 부른다.
• 택시 기하학은 특이하게도 유클리드 기하학의 5개 공준을 모두 만족한다. 
  • 하지만, 길이(=거리)에 대한 정의가 다르다 보니 유클리드 기하학과는 사뭇 다른 특성이 나타나며, 이런 이유로 비유클리드 기하학으로 분류된다.

 

맨해튼 거리(Manhattan Distance)

• 미국 뉴욕의 맨해튼처럼 바둑판 격자 모양으로 도로가 나있는 상황에서, 한 지점에서 다른 위치로 이동하기 위해서 필요한 거리
• 도로가 바둑판 격자처럼 되어 있으니 도로를 따라 이동해야 하는데, 이 때의 이동거리가 두 점 사이의 거리가 된다.

• 좌표계에 두점 `P, Q` 가 주어질 때, 두 점 사이의 거리는 아래와 같이 정의된다.

$$d(P, Q) = \sum_{i=1}^{n} | P_{i} - Q_{i}|$$

• 예) 2차원 평면에서 두 점 $P(p_{1}, p_{2})$ 와 $Q(q_{1}, q_{2})$ 에 대해서 두 점 사이의 거리는 다음과 같다.

$$d = |p_{1} - q_{1}| + |p_{2} - q_{2}|$$

 

유클리드 기하학에서의 원

• 정점에서 일정한 거리에 있는 점의 집합을 의미한다.
• 원의 넓이 : 반지름(`r`) × 반지름(`r`) × 원주율(`π`) = $πr^{2}$)
• 원의 방정식 : $(x - a)^{2} + (y - b)^{2} = r^{2}$ (원의 중심이 `(a, b)` 이고, 반지름이 `r` 일 때)

 

택시 기하학에서의 원

• 택시 기하학에서의 원은 두 대각선의 길이가 같은 마름모 모양의 정사각형이다. 
• 원의 정의가 정점에서 일정한 거리에 있는 점의 집합을 의미하는데 택시 평면 위에서는 정점에서의 거리가 같은 점의 집합이 마름모 모양의 정사각형이 된다. 
• 택시 평면 위에서 택시가 이동하는 거리가 동일한 점을 이어 보면 알 수 있다.
• 원의 넓이 : 2 × 반지름(`r`) × 반지름(`r`) = $2r^{2}$
• 원의 방정식 : $|x - a| + |y - b| = d$ (원의 중심이 `(a, b)` 이고, 거리가 `d` 일 때)

택시 기하학의 원