(14751) Leftmost Segment

https://www.acmicpc.net/problem/14751

단계별로 풀어보기

62단계(동적 계획법 최적화 1) 1번째

 

 

 

또 단계가 갑자기 건너뛰었는데 동적 계획법을 공부하다 동적 계획법 테크닉까지 공부해버려서 그렇다(정확히는 컨벡스 헐 트릭과 크누스 최적화). 이게 마지막인데 이 시점에서 알고리즘 이해가 어렵고(정확히는 수학 3 단계에서 폴라드 로 알고리즘에 대해 공부하다가) 이 이상으로 배우는 것은 너무 과투자 아닌가 하는 생각이 들어 단계별로 풀어보기를 더 나아는 것을 그만두고 지금까지 배운 코드를 복습하고 시뮬레이션 계열의 문제를 푸는 연습을 했기 때문이다.

 

아무튼 이 문제는 컨벡스 헐 트릭을 쓰기 위한 일차함수들의 최소값 함수를 구성하는 연습 문제다. 주어진 선분들을 (아래쪽 선과 만나는 x좌표-위쪽 선과 만나는 x좌표)가 큰 순서, 같으면 더 왼쪽에 있는 순서대로 정렬한다. 이제 정렬된 선분을 하나씩 탐색하며 스택을 이용해 가장 왼쪽에 있는 선분과 그 구간만 남길 것이다. 스택에 선분이 두 개 이상 있을 때, 새로운 선분이 스택의 맨 위 선분과 교차하는 Y좌표가 이전 두 선분의 교점(스택의 위쪽 두 선분)의 Y좌표보다 작다면 그냥 넣는다. 만약 크다면, 이 선분은 지금 탐색하는 구간 내에서 기존 선분보다 항상 왼쪽이므로 이전 두 선분의 교점 Y좌표보다 작아질 때까지(스택에서 빼면 다시 맨 위 두 선분의 교점으로 계산) 빼다가 집어넣는다. 결과적으로 스택에는 가장 왼쪽에 존재하는 선분들만 남아있게 되며, 이 스택과 저장된 구간을 이용해 이분 탐색으로 특정 Y좌표에서 가장 왼쪽에 있는 선분을 찾아낼 수 있다.

컨벡스 헐 트릭은 선분의 좌표를 이용해야 하는 특성 상 부동소수점 오차로부터 자유로울 수 없는데, 그래도 입력 특성 상 보통은 double이나 long double 정도면 충분히 통과 가능하다. 하지만 이 문제는 아니여서 부동소수점 오차를 피하기 위해 분자와 분모를 정수형으로 따로 저장하고 서로 곱해주는 방식으로 실수형이 나타나는 것을 피했다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<long,long> p;
typedef pair<int,p> LINE_t; // v[i]선분, 교점 p.first/p.second

long maxY, minY;

long ToLong(string s){
  int len= s.length();
  
  if(s[len-2]=='.') s+= "00", len+= 2;
  else if(s[len-3]=='.') s+= "0", len+= 1;
  
  s= s.substr(0,len-4)+s.substr(len-3);

  return stol(s);
}

pair<long,long> GetCrossY(p A, p B){
  long denominator= (B.first-B.second)-(A.first-A.second);
  long numerator= (maxY-minY)*(A.second-B.second) + minY*denominator;
  
  return {numerator,denominator};
}

int main() 
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  int n, m;
  
  cin >> maxY >> minY >> n;
  
  maxY*= 1000;  minY*= 1000;
  
  vector<pair<int,p>> v(n);
  
  for(int i=0;i<n;i++){
    v[i].first= i;
    cin >> v[i].second.first >> v[i].second.second;
  }
  
  sort(v.begin(), v.end(), [](pair<int,p> A, pair<int,p> B){
    long Aslope= A.second.second-A.second.first;
    long Bslope= B.second.second-B.second.first;
    
    if(Aslope==Bslope)  return A.second.first<B.second.first;
    return Aslope>Bslope;
  });
  
  vector<LINE_t> f;
  f.push_back({0,{maxY,1}});
  
  for(int i=1;i<n;i++){
    LINE_t now= {i,GetCrossY(v[f.back().first].second, v[i].second)};
    
    if(now.second.second==0 || now.second.first<=now.second.second*minY)  continue;
    
    while(!f.empty()){
      now.second= GetCrossY(v[f.back().first].second, v[i].second);
      
      if(f.back().second.first*now.second.second>now.second.first*f.back().second.second)  break;
      
      f.pop_back();
    }
    
    f.push_back(now);
  }
  
  cin >> m;
  
  while(m--){
    string s;
    
    cin >> s;
    
    long h= ToLong(s);
    
    int lo= 0, hi= f.size();
    while(lo+1<hi){
      int mid= (lo+hi)/2;
      
      (h*f[mid].second.second>=f[mid].second.first ? hi:lo)= mid;
    }
    
    cout << v[f[lo].first].first+1 << "\n";
  }
  
  return 0;
}