1909번 - 냄새 싫어 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 667 | 120 | 77 | 16.667% |
문제
월드 캠프가 계속될수록, 씻지 않아 냄새를 풍기는 사람들이 늘어 가고 있다. 이에 따라 당신은 교실에서 한 지점에서 다른 지점으로 이동할 일이 생겼을 때, 냄새나는 사람들이 앉아 있는 자리로부터 최대한 멀리 떨어진 경로를 따라 걸어가고 싶어졌다. 이를 해결하는 프로그램을 작성하라.
교실은 좌표 평면으로 표현된다. 친구들이 앉아 있는 좌표 (x,y), 시작지점과 목적지점의 좌표 (sx,sy), (tx,ty)는 교실의 가로 세로 크기 Wx, Wy에 대해 1≤x, sx, tx≤Wx, 1≤y, sy, ty≤Wy를 만족한다. Wx, Wy는 2≤Wx, Wy≤1,000를 만족한다. 냄새나는 사람들의 수 n은 1≤n≤Wx*Wy- 2 를 만족한다.
좌표 평면에서 x축 혹은 y축에 평행하게 (가로 혹은 세로 방향으로) 1만큼씩 움직여, 시작지점에서 목적지점까지 이동하며 거친 점들의 자취를 하나의 경로라고 한다. 단, 점들의 좌표는 항상 양의 정수를 유지해야 한다. 냄새나는 사람들과 어떤 경로와의 거리는, 경로 위의 임의의 점과, 임의의 냄새나는 사람들이 앉아 있는 점들 사이의 거리 중 가장 짧은 것으로 정의된다. 가능한 경로 중, 냄새나는 사람들과의 거리가 가장 먼 경로를 최적의 경로라고 할 수 있다.
여러분이 할 일은, 시작지점과 목적지점, 냄새나는 사람들이 앉아 있는 위치가 주어졌을 때, 최적의 경로를 따라 이동할 경우, 냄새나는 사람들과 경로와의 거리가 얼마인지 구하는 것이다.
입력
첫 줄에 교실의 크기를 나타내는 두 정수 Wx, Wy가 주어진다. 둘째 줄에는 시작지점과 목적지점의 좌표를 나타내는 네 정수 sx, sy, tx, ty가 주어진다. 셋째 줄에는 냄새나는 사람들의 수 n이 주어진다. 넷째 줄부터는 한 줄에 하나씩 냄새나는 사람들이 앉아있는 곳의 좌표 xi, yi가 주어진다. 시작지점과 도착지점에는 냄새나는 사람들이 앉아있지 않다.
출력
최적의 경로로 이동할 때, 냄새나는 사람들과 경로와의 거리가 얼마인지를 구해서, 첫 줄에 그 제곱값을 출력한다. 무슨 수를 쓰더라도 냄새나는 사람들이 있는 위치를 피해갈 수 없을 경우, 출력값은 0이 된다.
예제 입력 1
5 5 1 1 5 5 2 3 3 4 2
예제 출력 1
4
힌트
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호