내비게이션

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

현대오토에버의 내비게이션 소프트웨어는 안전하고 편리한 이동 경험을 구현한다. 전 세계 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 \le N \le 1\,000$)

두 번째 줄에 시작점과 도착점의 좌표 $s\_x$, $s\_y$, $e\_x$, $e\_y$가 공백으로 구분된 네 정수로 주어진다. ($-10^9 \le s\_x, s\_y, e\_x, e\_y \le 10^9$)

그다음 줄부터 1번 내비게이션부터 $N$번 내비게이션까지의 데이터가 차례로 주어진다. 각 내비게이션의 입력은 다음과 같다.

• 첫 번째 줄에 순서대로 방문해야 하는 중간 지점의 개수 $M\_i$가 주어진다. ($1 \le M\_i \le 100$)
• 두 번째 줄부터 $M\_i$개의 줄에 걸쳐 $j$번째로 방문해야 하는 중간 지점 $(x\_{i,j}, y\_{i,j})$의 $x$좌표와 $y$좌표가 공백으로 구분된 두 정수로 주어진다. ($-10^9 \le x\_{i,j}, y\_{i,j} \le 10^9$)

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