Subtask 1

Với điểm ~A_i(x_i, y_i)~ và đường thẳng ~\Delta: y = ax + b~, khoảng cách từ ~A_i~ đến ~\Delta~ là: ~d(A_i, \Delta) = \frac{|ax_i - y_i + b|}{\sqrt{a^2 + 1}}.~

Xét các đường thẳng ~\Delta~ cố định, đáp án cần tìm chính là điểm ~i~ sao cho ~|ax_i - y_i + b|_{max}~.

Độ phức tạp: ~O(n \times q)~.

Subtask 2

Ta có nhận xét quan trọng: ~|ax_i - y_i + b|_{max} \Leftrightarrow (ax_i - y_i)_{min}~ hoặc ~(ax_i - y_i)_{max}~.

Do ở subtask này, ~a~ chỉ nhận hai giá trị ~0~ và ~1~, ta có thể dễ dàng tìm trước các vị trí thỏa mãn biểu thức trên trong ~O(n)~ rồi trả lời từng truy vấn trong ~O(1)~.

Độ phức tạp: ~O(n + q)~.

Subtask 3

Từ nhận xét ở subtask 2, ta có thể tiếp tục cải tiến thuật toán. Sử dụng Convexhull trick để tìm ~(ax_i - y_i)~ lớn nhất và nhỏ nhất (Đường thẳng trong đề trở thành điểm, và điểm trong đề bài trở thành các đường thẳng trong Convexhull trick).

Độ phức tạp: ~O(q \times log_{2}n)~.

P/S: Hãy thử giải bài toán này, nhưng với mỗi đường thẳng ~\Delta~ ta cần tìm ~k \le 5~ điểm xa ~\Delta~ nhất.

#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
struct CHT
{
    vector<pair<int, int>> line[2];
    vector<pair<ld, int>> vc[2];
    ld intersect(pair<int, int> p, pair<int, int> q)
    {
        return (ld)(q.se - p.se) / (p.fi - q.fi);
    }
    void add(pair<int, int> x, int id, bool type)
    {
        while(vc[type].size() > 1 || (vc[type].size() == 1 && line[type].back().fi == x.fi))
        {
            if(line[type].back().fi == x.fi)
            {
                if(type)
                {
                    if(line[type].back().se > x.se)
                    {
                        line[type].pop_back();
                        vc[type].pop_back();
                        continue;
                    }
                    else return;
                }
                else
                {
                    if(line[type].back().se < x.se)
                    {
                        line[type].pop_back();
                        vc[type].pop_back();
                        continue;
                    }
                    else return;
                }
            }
            if(intersect(x, line[type][line[type].size() - 2]) >= intersect(x, line[type].back()))
            {
                line[type].pop_back();
                vc[type].pop_back();
            }
            else break;
        }
        if(vc[type].empty()) vc[type].pb({-oo, id});
        else vc[type].pb({intersect(x, line[type].back()), id});
        line[type].pb(x);
    }
    pair<int, int> get(ld x, int type)
    {
        int i = upper_bound(vc[type].begin(), vc[type].end(), pair<ld, int> {x, 0}) - vc[type].begin() - 1;
        return {line[type][i].fi * x + line[type][i].se, vc[type][i].se};
    }
};
int n, q;
pair<int, int> a[maxN];
int id[maxN];
void ReadInput()
{
    cin >> n >> q;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i].fi >> a[i].se;
        a[i].fi *= -1;
    }
    iota(id + 1, id + n + 1, 1);
}
void Solve()
{
    sort(id + 1, id + n + 1, [](int i, int j)
    {
        return (a[i].fi < a[j].fi || (a[i].fi == a[j].fi && a[i].se < a[j].se));
    });
    CHT cht;
    for(int i=1; i<=n; i++)
        cht.add(a[id[i]], id[i], 0);
    for(int i=n; i>=1; i--)
        cht.add(a[id[i]], id[i], 1);
    while(q--)
    {
        int x, y;
        cin >> x >> y;
        pair<int, int> val1 = cht.get(x, 0), val2 = cht.get(x, 1);
        int dist1 = abs(y - val1.fi), dist2 = abs(y - val2.fi);
        int pos = (dist1 > dist2 ? val1.se : val2.se);
        cout << pos << '\n';
    }
}
#define taskname "highway"
int32_t main()
{
    if (fopen(taskname ".inp", "r"))
    {
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    for(int itest=1; itest<=T; itest++)
    {
        ReadInput();
        Solve();
    }
}