KOI 1차 2020 고3- 조명등 > 문제은행 : 정보올림피아드&알고리즘




4522 : 조명등

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
41 회   
시도횟수
138 회   

문제

관광지로 유명한 아르미 도시에서는 아래 <그림 1>에서 보는 것처럼 일직선으로 된 길을 따라 자그만 조각품을 창대 끝에 달아 두었다.

장대의 높이와 장대의 간격은 설치자의 예술 감각에 따라 다양하다.



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


장대 끝에 달린 조각품이 야간에도 모두 다 잘 보일 수 있도록 하기 위해 조명등을 설치하려고 한다.
조명등 역시 장대 끝에 설치하는데, 조명등 위에 있는 갓 때문에 아래 방향 좌우 45° 범위 내에 있는 공간만 밝게 비춘다.
조명등은 필요한 곳에 새로운 장대를 세워 그 끝에 설치하는데, 이미 조각품이 설치된 곳에도 조명등을 설치할 수 있다.

아래 <그림 2>는 <그림 1>에서 보인 5개의 조각품을 비추기 위해 3개의 조명등을 설치한 예를 보여준다.
처음 두 조명등은 새로운 위치에 막대를 세워 그 끝에 조명등을 설치하였고, 세 번째 조명등은 설치된 조각 위치와 동일한 곳에 설치되었다.


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


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


<그림 3>조명등을 1개만 설치한 예


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

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

 ​​

 


입력형식

여러분 프로그램의 한 실행에서 여러 개의 테스트 케이스를 풀어야 한다.

 

입력의 첫 줄은 전체 테스트 케이스의 수 T이다.(1≤T≤​100)

 

각 테스트 케이스의 첫 줄에는 조각품의 개수 N이 주어진다.(1≤​N≤​100,000)

다음 N개의 줄에는 각 조각품의 위치 x좌표 xi와 높이 hi가 정수로 주어진다.(1≤​xi,hi≤​100,000,000)

 

조각품들은 x좌표가 증가하는 순서로 주어진다. 모든 테스트 케이스에서 N들의 합은 1,000,000이하이다.


출력형식

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

 

 

추가 제약 조건

 

5점 상당의 테스트케이스에서 N≤​3을 만족한다.

30점 상당의 테스트케이스에서 N≤​1,000을 만족한다.

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


입력 예

2
2
3 1
13 2
2
3 2
4 2

출력 예

5.00
6.25

데이타 만든사람 : ohjtgood,wram Ly

DP, CHT, Convex Hull Trick

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP