2022.01.27 [백준] C# 택시 기하학

 

 

 

 

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

3053번: 택시 기하학

 

 

---

풀이 

 

https://itholic.github.io/kata-taxicab-circle/

[kata][python] 택시 기하학에서의 원 넓이 구하기

위 블로그에서 택시 기하학에 대한 내용  가져왔습니다.

 

유클리드 기하학에서의 두 지점의 거리는 좌표평면상의 최단거리를 의미한다.

하지만 실제 도시에서 두 지점의 거리는 좌표평면상의 최단거리와 다르다.

 

택시가 한 지점에서 다른 지점으로 이동하는 것을 상상해보자.

택시는 건물을 뚫고 지나가지 못하기때문에 좌회전도하고 우회전도한다.

구불구불 굽어진 길을 가다보면 어느새 목적지에 도착하는데,

이 때 출발지점 T1(x1, y1)과 도착지점 T2(x2, y2) 사이의 거리를 구하는 공식은 다음과 같다.

D(T1, T2) =

x1 - x2

+

y1 - y2

 

공식을 깊이 이해할 필요는 없다.

원리만 생각해보자.

모눈종이 위에 임의의 점 T1, T2를 찍어 놓았다고 상상해보자.

그리고 T1에서 T2로 가기 위한 방법을 생각해보자.

 

모눈종이를 가로질러서 직선을 긋는게 가장 빠르겠지만 (유클리드 거리).

모눈종이에 그어져있는 선만 따라서 이동할 수 있다고 가정하자.

그럼 다음과 같은 경로들이 가능할 것이다.

그림출처: 위키백과

이 때, 모눈종이를 가로지르는 초록색 선이 유클리드 거리이자 최단거리이다.

하지만 모눈종이의 선만 따라 이동할 수 있다고 했으므로, 이 경우는 제외하자.

그리고 나머지 빨간색, 파란색, 노란색 선은 모두 거리가 12로 같다.

 

위에서 적었던 공식은 그냥 이 거리를 구하는 공식이다.

빨간색 선의 세로길이를 보면 y2 - y1이다.

빨간색 선의 가로길이를 보면 x2 - x1이다.

즉, 총 길이는 이 둘을 합한 (y2 - y1) + (x2 - x1) 이다.

이걸 좀 더 일반적으로 정리한게 앞에서 언급한 |x1 - x2| + |y1 - y2| 인 것이다.

 

그럼, 택시 기하학에서의 원은 어떤 모양일까?

원이란 ‘평면상의 어떤 점에서 거리가 일정한 점들의 집합’이다.

거리가 일정하므로, 유클리드 기하학에서의 원은 우리가 흔히 알고있는 동그라미 모양이다.

하지만 택시 기하학에서의 원은 좀 다르다.

한 점에서 택시 기하학적 거리가 같은 모든 점을 그려 연결하면 다음과 같은 마름모 꼴이 나온다.

그림출처: 조선pub

조금 혼란스러울수도 있는데,

원점부터 선만 따라서 마름모를 이루는 각 점에 도착하는 거리를 재보면 3으로 모두 같다는것을 알 수 있다.

그리고 이 원의 반지름 또한 3이다.

원점에서 (3, 0)과 (0, 3) 까지 닿는 길이를 생각해보자.

 

즉, 택시 기하학에서의 반지름이 R인 원의 넓이란,

“두 대각선의 길이가 2R인 마름모의 넓이” 와 같다.

마름모의 넓이는 한 대각선(2R)에서 다른 대각선을 2등분한 길이(R)를 곱해주면 된다.

즉, 택시 기하학에서 반지름이 R인 원의 넓이는 2R2 이다.

using System;
class Program{
    static void Main(){
        int r = int.Parse(Console.ReadLine());
        Console.WriteLine(Math.PI*r*r);
        Console.WriteLine(2*r*r);
    }
}