백준 19943 (C++) 조명등

최초 업로드: 2025-12-02 11:52:20

최근 수정 시간: 2025-12-02 11:52:53

게시자: rlatjwls3333

카테고리: 백준

# [Diamond IV] 조명등

[문제 링크](https://www.acmicpc.net/problem/19943)

## 문제 설명

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

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

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

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

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

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

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

## 입력

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

## 출력

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

## 풀이
먼저 어떤 조명을 비췄을 때, 그 공간에 포함되는 무의미한 점을 지워내야합니다. 조명등의 왼쪽 부분에서는 해당 점의 기울기가 -1인 그래프의 y절편보다 작거나 같은 점들을 뽑아냄으로 제외를 했고, 오른쪽 부분에서는 해당 점의 기울기가 1인 그래프의 y절편보다 크다면 넣어줌으로써 제외를 했습니다.

두 조명등을 모두 키지 않고 공통된 범위 하나만 킴으로써 더 최적이 되는 경우가 있습니다. 이 점의 y좌표를 구해보면 $(x_i - x_j + y_i + y_j)/2$ 이고 이 점에서의 조명등의 비용은 $((x_i - x_j + y_i + y_j)/2)^2$입니다.

dp[i]를 i번째 점까지 포함했을 때의 최소비용이라 두면 dp[i] = dp[j] + $((x_i - x_j + y_i + y_j)/2)^2$라 둘 수 있습니다.

식을 정리하고 $-x_j+y_j$를 기울기로 두면 처음에 이 값이 항상 감소하도록 점을 남겨놓았기에 CHT를 사용하여 최적화를 할 수 있습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll dp[100'001];
string ret[4] = {".00", ".25", ".50", ".75"};

struct element {
    ll a, b;
    double x=-1e150;
};

double meetX(element a, element b) {
    return (double)(a.b-b.b)/(b.a-a.a);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 while(t--) {
 int n; cin >> n;
 vector<pair<int, int>> v;
 while(n--) {
 int x, h; cin >> x >> h;
 while(!v.empty() && h-x>=v.back().second-v.back().first) v.pop_back();
 if(v.empty() || x+h>v.back().first+v.back().second) v.push_back({x, h});
 }

vector<element> stk;
 for(int i=1;i<=v.size();i++) {
 ll xi = v[i-1].first, yi = v[i-1].second;
 ll A = xi+yi, B = -xi+yi;
 ll x = 2*A;
 element cur = {B, B*B+dp[i-1]};
 while(!stk.empty()) {
 cur.x = meetX(cur, stk.back());
 if(cur.x>stk.back().x) break;
 stk.pop_back();
 }
 stk.push_back(cur);

int left=0, right=stk.size()-1;
 while(left<right) {
 int mid = left+right+1>>1;
 if(x<stk[mid].x) right=mid-1;
 else left=mid;
 }
 dp[i] = stk[left].a*x+stk[left].b + A*A;
 }
 cout << dp[v.size()]/4 << ret[dp[v.size()]%4] << '\n';
 }
}
```