직선과 쿼리 1 (JUNGOL 3671)

https://jungol.co.kr/problem/3671

---

아이디어

CHT를 이용해주면 됩니다. 기울기가 작은 것부터 차례대로 넣으면서 볼록 껍질을 만들어줍시다. 그리고 x가 주어지는 쿼리들은 다 모아놓은 다음에 정렬해서 한번에 처리해줍니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

void minimize(vector <pair <ll,ll> > &v)
{
    sort (v.begin(),v.end());

    vector <pair <ll,ll> > res;
    for (ll i=0;i<v.size();i++)
    {
        if (i==v.size()-1 || v[i].first!=v[i+1].first)
            res.push_back(v[i]);
    }

    v=res;
}

double GetCross(pair <ll,ll> A,pair <ll,ll> B)
{
    return (double)(A.second-B.second)/(double)(B.first-A.first);
}

vector <pair <double,ll> > CHT(vector <pair <ll,ll> > &v)
{
    //v:{a,b}의 집합
    //res:{교점의 x좌표,직선의 번호}

    sort (v.begin(),v.end());

    ll sz=1,N=v.size();
    vector <pair <double,ll> > res;
    res.push_back({-1e18,0});
    
    for (ll i=1;i<N;i++)
    {
        while (GetCross(v[i],v[res.back().second])<=res.back().first) //기존 교점보다 왼쪽이면
            res.pop_back();
        res.push_back({GetCross(v[i],v[res.back().second]),i});
    }

    return res;
}

ll Answer[505050]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,Q,i,a,b,x;
    vector <pair <ll,ll> > v;

    cin>>N>>Q;
    for (i=0;i<N;i++)
    {
        cin>>a>>b;
        v.push_back({a,b});
    }

    minimize(v);
    auto res=CHT(v);

    vector <pair <ll,ll> > nums;
    for (i=0;i<Q;i++)
    {
        cin>>x;
        nums.push_back({x,i});
    }

    sort (nums.begin(),nums.end(),greater<>());

    for (i=0;i<Q;i++)
    {
        while (res.back().first>nums[i].first) //교점보다 현재 x좌표가 왼쪽이면
            res.pop_back();
        Answer[nums[i].second]=v[res.back().second].first*nums[i].first+v[res.back().second].second;
    }

    for (i=0;i<Q;i++)
        cout<<Answer[i]<<"\n";
}