관광지로 유명한 아르미 도시에서는 아래 <그림 1>에서 보는 것처럼 일직선으로 된 길을 따라 자그만 조각품을 장대 끝에 달아 두었다. 장대의 높이와 장대의 간격은 설치자의 예술 감각에 따라 다양하다.

<그림 1> 5개의 조각품이 설치된 모습

장대 끝에 달린 조각품이 야간에도 모두 다 잘 보일 수 있도록 하기 위해 조명등을 설치하려고 한다. 조명등 역시 장대 끝에 설치하는데, 조명등 위에 있는 갓 때문에 아래 방향 좌우 45° 범위 내에 있는 공간만 밝게 비춘다. 조명등은 필요한 곳에 새로운 장대를 세워 그 끝에 설치하는데, 이미 조각품이 설치된 곳에도 조명등을 설치할 수 있다. 아래 <그림 2>는 <그림 1>에서 보인 5개의 조각품을 비추기 위해 3개의 조명등을 설치한 예를 보여준다. 처음 두 조명등은 새로운 위치에 막대를 세워 그 끝에 조명등을 설치하였고, 세 번째 조명등은 설치된 조각 위치와 동일한 곳에 설치되었다.

<그림 2> 조명등이 설치된 예

<그림 3>은 조명등을 1개만 설치하여 전체 조각품을 비추는 예를 보여준다.

조명등을 높이 달수록 더 많은 면적을 밝게 할 수 있지만, 그에 비례하여 더 비싼 등을 달아야 한다. 즉, 각 조명등의 설치 비용은 그 조명등이 밝히는 삼각형 모양의 면적이다.

설치된 모든 조각품을 비추기 위해 최소 비용으로 조명등을 설치하려고 한다.

5점 상당의 테스트케이스에서 \(N \le 3\)을 만족한다.

30점 상당의 테스트케이스에서 \(N \le 1, 000\)을 만족한다.

20점 상당의 테스트케이스에서 모든 \(h_i\)가 같음을 만족한다.

45점 상당의 테스트 케이스는 추가적인 제약 조건이 없다.

첫 줄에 테스트 케이스의 수 \(T\)가 주어진다. 각 테스트 케이스의 첫 줄에는 조각품의 개수 \(N\)이 주어진다. 다음 \(N\)개의 줄에는 각 조각품의 위치 \(x\) 좌표 \(x_i\)와 높이 \(h_i\)가 주어진다. 조각품은 \(x\) 좌표가 증가하는 순서로 주어진다.

각 테스트 케이스에 대해서 한 줄에 최소 비용을 소수점 아래 둘째 자리까지 정확하게 출력한다.

rip 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2020 > 1차 대회 > 고등부 3번