[BOJ/백준] 25558 - 내비게이션

25558번: 내비게이션

---

맨해튼거리

+

long long

---

---

• 제목

내비게이션

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

위치 기반 서비스 분야의 독보적인 기술력

 

현대오토에버의 내비게이션 소프트웨어는 안전하고 편리한 이동 경험을 현실로 구현하여 전 세계 70여 개 국가에서 사용되며 글로벌 인포테인먼트 시장을 리드하고 있습니다.

다양한 콘텐츠와 서비스를 갖춘 최첨단 내비게이션 소프트웨어를 통해 고객에게 보다 풍부한 모빌리티 경험과 혁신적인 가치를 선사합니다.

지리정보시스템(GIS)과 위치기반서비스(LBS) 분야의 독보적인 기술과 정교한 데이터와 경로탐색 알고리즘을 이용한 고도화된 내비게이션 솔루션으로 완성차의 글로벌 진출에 발맞춰 세계 시장을 견인하고 있습니다.

 

고객 최우선의 가치 실현
차량 내비게이션

현대오토에버는 다양한 내비게이션 소프트웨어를 통해 전 세계 고객들이 목적지까지 빠르고 안전하게 주행할 수 있도록 하는 고객 최우선의 가치를 실현하고 있습니다.

이를 위해 센터 통신을 기반으로 사용자의 현 위치를 실시간으로 파악한 후 도로의 소통 상황이나 통제 구간 등 교통의 흐름에 영향을 주는 요소들에 대한 정보를 제공합니다.

ICPC Sinchon은 현대 오토에버로부터 차량 내비게이션의 테스트를 요청받았다. 운영진들은 현대 오토에버의 OEM 순정 내비게이션의 성능과 그 외 $N-1$개의 타사의 내비게이션의 성능을 비교했고, OEM 순정 내비게이션이 다른 내비게이션보다 더 효율적인 목적지까지의 최적 경로를 탐색하는 것을 확인할 수 있었다.

이에 대한 실험 데이터를 SUAPC 2022 Summer가 끝나고 나서 현대 오토에버에게 전달하고자 한다. 실험 데이터는 다음과 같은 정보들을 담고 있다.

시작점 (s_x, s_y)와 도착점 (e_x, e_y)$
각 내비게이션의 시작점 (s_x, s_y)에서 도착점 (e_x, e_y)까지 도달하기 위해서 순차적으로 방문해야 하는 중간 지점들의 위치

두 지점 간의 거리는 맨해튼 거리로 정의된다. 즉, (a,b)와 (c,d)와의 거리는 |a-c|+|b-d|이다. 그리고 각 내비게이션이 안내한 목적지까지의 최적 경로의 거리는 서로 다르다.

그러나 SUAPC 2022 Summer 대회 당일에 컴퓨터의 갑작스러운 고장으로 인해 각 내비게이션에 대한 실험값들이 서로 뒤바뀌었다. 대회가 끝나기 전에 각 내비게이션의 데이터가 주어졌을 때, 어느 데이터가 OEM 순정 내비게이션인지 찾아보자.

---

• 입력

첫 번째 줄에 실험에 사용한 내비게이션의 개수를 의미하는 양의 정수 $N$이 주어진다. (2 ≤ N ≤ 1000)

두 번째 줄에 시작점과 도착점의 좌푯값을 의미하는 s_x, s_y, e_x, e_y를 의미하는 네 정수가 공백으로 구분되어 주어진다. (-10^9 ≤ s_x, s_y, e_x, e_y ≤ 10^9)

그다음 줄에는 $1$번 내비게이션부터 $N$번 내비게이션의 데이터에 대한 입력이 순차적으로 주어진다. 각 내비게이션에 대한 입력은 다음과 같이 주어진다.

첫 번째 줄에는 순차적으로 방문해야 하는 중간 지점들의 위치의 개수인 M_i가 주어진다. (1 ≤ M_i ≤ 100)
두 번째 줄부터 M_i개의 줄에 걸쳐서 $j$번째로 방문해야 하는 중간 지점 (x_{i,j}, y_{i,j})의 x좌표와 y좌표의 값을 의미하는 두 정수가 공백으로 구분되어 주어진다. (-10^9 ≤ x_{i,j}, y_{i,j} ≤ 10^9)

---

• 출력

OEM 순정 내비게이션에 해당하는 데이터 번호를 출력하여라.

---

예제 입력1	예제 출력1
0 0 10 10 2 11 1 9 9 2 1 12 9 9 2 5 5 9 9	3

---

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
using namespace std;
#define endl '\n'
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main() {
    fastio;
    long long tc, sx, sy, ex, ey, sz, minIdx = -1;
    long long minSum = LLONG_MAX;
    vector<long long> navi;
    cin >> tc >> sx >> sy >> ex >> ey;
    for(int n = 0 ; n < tc ; n++){
    	cin >> sz;
    	long long sum = 0;
		long long prevx = sx, prevy = sy, x, y;
    	for(int m = 0 ; m < sz ; m++){
    		cin >> x >> y;
    		sum += abs(x - prevx) + abs(y - prevy);
    		prevx = x;
    		prevy = y;
		}
    	sum += abs(ex - prevx) + abs(ey - prevy);
		if(minSum > sum){
			minIdx = n + 1;
			minSum = sum;
		}
	}
	cout << minIdx << endl;
    
	return 0;
}