백준 23282 (C++) Line Fighter 2

최초 업로드: 2025-11-04 00:30:38

최근 수정 시간: 2025-11-04 00:30:38

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] Line Fighter 2

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

## 문제 설명

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. <a href="/problem/1632">전편</a>에서 N개의 직선을 가지고 성공적인 놀이를 만들어낸 원숭이는 이제 또 다른 문제를 만들어내고야 말았다!!

문제는 정말 간단하다. 좌표평면상에 N개의 직선이 주어진다. 그리고 Q개의 질문이 주어진다. 각 질문은 (x, a)로 이루어져 있는데 a가 1이면 그 x값에서 N개의 직선 중의 최대값을 구하고, a가 2면 그 x값에서 N개의 직선 중의 최소값을 구하면 된다.

N개의 직선 중에는 축과 평행한 직선은 없다. N개의 직선과 Q개의 질문이 주어졌을 때, 각 질문에 답을 하는 프로그램을 작성하시오.

## 입력

첫째 줄에 직선의 개수 N과 질문의 개수 Q가 주어진다. N은 1이상 100,000이하의 정수이고, Q는 0이상 100,000이하의 정수이다. 그 다음부터 N줄에 걸쳐 각 직선의 정보가 주어진다. 각 직선을 y = ax+b로 나타냈을 때의 a, b가 주어진다. a, b는 -10,000이상 10,000이하의 정수이다. 그 다음부터 Q줄에 걸쳐 질문이 주어진다. 각 질문은 x a의 형식으로 들어온다. x는 -1,000,000.0이상 1,000,000.0이하인 실수이고 소숫점 첫째자리 안으로 주어진다. a는 1 또는 2이다.

## 출력

Q줄에 걸쳐 각 질문에 알맞은 실수를 출력한다. 절대 오차는 10-4까지 허용한다.

## 풀이
기울기가 전부 주어졌기에 CHT를 사용하였다.
기울기를 내림차순 정렬하여 최솟값을 찾아주었고, 오름차순 정렬하여 최댓값을 찾아주었다.

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

typedef long long ll;
typedef pair<ll, ll> P;

struct element {
    ll a, b;
    double x=INT_MIN;
};

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 n, q; cin >> n >> q;
 vector v(n);
 for(int i=0;i<n;i++) cin >> v[i].first >> v[i].second;

sort(v.begin(), v.end(), greater());
 vector<element> minStk;
 for(int i=0;i<n;i++) {
 element cur = {v[i].first, v[i].second};
 while(!minStk.empty() && minStk.back().a==cur.a) minStk.pop_back();
 while(!minStk.empty()) {
 cur.x = meetX(minStk.back(), cur);
 if(cur.x>minStk.back().x) break;
 minStk.pop_back();
 }
 minStk.push_back(cur);
 }

sort(v.begin(), v.end());
 vector<element> maxStk;
 for(int i=0;i<n;i++) {
 element cur = {v[i].first, v[i].second};
 while(!maxStk.empty() && maxStk.back().a==cur.a) maxStk.pop_back();
 while(!maxStk.empty()) {
 cur.x = meetX(maxStk.back(), cur);
 if(cur.x>maxStk.back().x) break;
 maxStk.pop_back();
 }
 maxStk.push_back(cur);
 }

cout << fixed << setprecision(4);
 while(q--) {
 double x; int a; cin >> x >> a;
 if(a==1) {
 int left=0, right=maxStk.size()-1;
 while(left<right) {
 int mid = left+right+1>>1;
 if(x<maxStk[mid].x) right=mid-1;
 else left=mid;
 }
 cout << maxStk[left].a*x+maxStk[left].b << '\n';
 } else {
 int left=0, right=minStk.size()-1;
 while(left<right) {
 int mid = left+right+1>>1;
 if(x<minStk[mid].x) right=mid-1;
 else left=mid;
 }
 cout << minStk[left].a*x+minStk[left].b << '\n';
 }
 }
}
```