Editorial for Bedao OI Contest 2 - Xây dựng cao tốc
Submitting an official solution before solving the problem yourself is a bannable offence.
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(); } }
Comments