2524번 - 희원이의 뉴욕 생활 스페셜 저지

뉴욕은 미국의 북동부, 뉴욕 주의 남쪽 끝에 있는 도시이다. 이곳은 미국에서 가장 인구가 많은 도시로, 세계에서 가장 인구가 많은 대도시 중 하나이다. 뉴욕은 세계적인 대도시로, 상업, 금융, 미디어, 예술, 패션, 연구, 기술, 교육, 엔터테인먼트 등 많은 분야에 걸쳐 큰 영향을 미친다. 또한 뉴욕에는 유엔 본부가 위치하고 있어 국제 외교에 있어 중요한 중심지이며, 세계의 문화 수도로 불리기도 한다.

뉴욕 항은 세계에서 가장 큰 자연적 항구 중 한 곳이며, 뉴욕은 맨해튼, 브루클린, 퀸스, 브롱크스, 스태튼아일랜드와 같은 다섯 개의 자치구로 나눠져있다. 이 자치구들은 각각 독립되어 있었다가 1898년 뉴욕에 합병되었다. 뉴욕의 인구는 2011년을 기준으로 8,244,910만 명으로 305 평방 마일 (790㎢)에 걸쳐 분산되어있다. 뉴욕은 미국에서 인구 밀도가 가장 높은 주요한 도시이다. 뉴욕은 800개 넘는 언어가 사용되는데, 세계에서 가장 다양한 언어가 공존하는 도시이다. 뉴욕 대도시권에는 6,720 평방 마일(17,400㎢)에 걸쳐 1,890만 명의 인구가 살고있다.

뉴욕은 1624년 네덜란드 공화국의 이주민들이 무역항으로서 설립했고, 1626년 네덜란드인들이 뉴 암스테르담이라는 지명을 붙였다. 1664년에는 영국인들이 강제 점령해 도시와 그 주변 지역을 통치했고, 찰스 2세가 동생 요크공에게 땅을 주면서 뉴욕이라 부르기 시작했다. 뉴욕은 1789년부터 1791년까지 미국의 공식적인 수도였다. 1790년부터는 미국에서 가장 큰 도시로 성장했다. 이후 19세기 말부터 20세기 초까지 수 백만의 이민자들이 배를 타고 뉴욕으로 왔다. 그리고 민주주의는 미국의 상징으로 세계적 인정을 받았다.

뉴욕에는 5번 애버뉴를 포함한 거리, 자유의 여신상을 포함한 랜드마크가 많이 있으며, 연간 5천만명의 관광객이 방문한다. 타임스 스퀘어는 세계의 교차로라고 불리며, 브로드웨이 연극이 상연된다. 또한, 뉴욕은 엔터테인먼트 산업의 중심지이다. 엠파이어 스테이트 빌딩을 포함한 초고층 건물, 센트럴 파크를 포함한 공원, 다리도 많이 있다. 로어맨해튼에는 월 스트리트가 있어, 경제 수도로도 불린다. 그리고, 월 스트리트에는 뉴욕 증권거래소도 위치하고 있다. 맨해튼의 부동산 시장은 세계에서 가장 비싸다. 뉴욕 지하철은 세계 최대의 지하철망이며, 컬럼비아 대학교, 뉴욕 대학교를 포함한 수많은 대학교도 뉴욕에 위치하고 있다. 뉴욕 양키스는 뉴욕의 메이저 리그 야구 팀으로, 뉴욕의 상징으로도 볼 수 있다.

뉴욕은 잠들지 않는 도시, 빅 애플, 고섬 등의 애칭이 있다. 2012년, 싱크탱크가 발표한 사업, 인재, 문화, 정치 등을 대상으로 한 종합적인 세계 도시 순위에서 세계 1위의 도시로 평가되었다. (출처: 위키백과)

이 곳이 바로 희원이가 사는 곳이다.

희원이는 뉴욕의 맨해튼에 살고 있다. 

맨해튼(Manhattan)은 뉴욕의 자치구 중 가장 인구 밀도가 높은 자치구로, 허드슨 강에 있는 섬을 포함하여 본토의 몇 블록을 포함하는 지역을 가리킨다. 맨해튼은 뉴욕 군(New York County)과 동일한 영토로, 뉴욕 주의 군이 된다. 자치구와 군으로 구성된 맨해튼 섬(Manhattan Island)은 루스벨트 섬, 랜들스아일랜드, 워즈 섬, 거버너스 섬, 리버티 섬, 밀 록, 엘리스 섬과 같은 작은 섬들을 포함하고 있다. 브롱크스와 밀접해있는 지역인 마블힐까지 포함한다.

뉴욕 군은 미국에서 가장 인구 밀도가 높은 군이며, 세계에서도 가장 인구 밀도가 높은 지역이다. 2010년 인구조사에 의하면, 인구는 1,585,873명이다. 또한, 미국의 군 중 가장 부유한 군으로, 2005년 기준으로 1인당 소득은 100,000달러를 넘었다. 맨해튼은 뉴욕의 자치구 중에서 3번째로 인구가 많으며, 면적으로는 제일 작다.

맨해튼은 미국에서 상업적, 재정적, 문화적으로 중요한 장소이다. 로어맨해튼에는 뉴욕 증권거래소와 NASDAQ이 있는 월 스트리트가 있다. 뉴스, 잡지, 책과 같은 여러 대중 매체의 출판업자들뿐만 아니라 미국에 있는 대부분의 주요한 라디오, 텔레비전, 통신 회사들이 이곳에 기반을 두고 있다.

맨해튼에는 유명한 랜드마크, 관광지, 박물관, 대학교가 많다. 또한 국제 연합 본부가 있는 곳이다. 맨해튼은 뉴욕과 뉴욕 대도시권의 중심지이며, 비즈니스, 엔터테인먼트 활동의 중심지이기도 하다. 그 결과, 뉴욕의 다른 자치구인 브루클린과 퀸스 지역 주민들은 맨해튼에 여행 가는 것을 종종 "도시로 간다."라고 표현하기도 한다. (출처: 위키백과)

맨해튼은 도시가 직사각형 격자판 모양이다. 그래서 코너 A(Ax,Ay)에서 코너 B(Bx,By)로  갈 때, 가장 짧은 거리는 |Ax-Bx| + |Ay-By| 이다.

하지만, 위와 같은 계산 방법은 브로드웨이를 고려하지 않는다. 브로드웨이는 이런 격자를 비스듬히 가로질러서 가는 큰 도로이다.

브로드웨이는 브로드웨이(영어: Broadway)는 미국 뉴욕 주 슬리피할로에서 시작되어 뉴욕 맨해튼 남쪽 끝까지 이어지는 거리이며, 그 근처 지역을 뜻하는 지역명이다. 브로드웨이에서 제일 번화한 곳은 타임스 스퀘어와 그 부근 지역이다. (출처: 위키백과)

희원이가 현재 있는 곳 A와 가려고하는 곳 B의 좌표와, 브로드웨이의 정보가 주어진다. 이때, A에서 B로 가는 가장 짧은 경로의 길이를 구하는 프로그램을 작성하시오.

맨해튼의 도로는 총 3가지 종류가 있는데, 아래와 같이 표현한다.

• 모든 정수 Z에 대해서, avenue는 x = Z로 표현한다.
• 모든 정수 Z에 대해서, street는 y = Z로 표현한다.
• 브로드웨이는 방정식 Px+Qy = R로 표현한다.

  A에서 B로 갈 때, 도로가 교차하는 지점에서만 도로를 바꿀 수 있다.

처음 4개의 숫자는 Ax, Ay, Bx, By이다. (A=(Ax,Ay), B=(Bx,By)

다음 3개 숫자 P, Q, R은 위에서 설명한 브로드웨이를 나타내는 방정식이다. 

A에서 B로 가는 가장 짧은 길이를 출력한다. 절대/상대 오차는 10^-9까지 허용한다.