PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raju511
Tester: satyam_343
Editorialist: iceknight1093
DIFFICULTY:
3580
PREREQUISITES:
Math, Fenwick/segment trees
PROBLEM:
A set S of points is said to belong to a line of slope m, within tolerance D, if there exists a line of slope m that’s at most vertical distance D away from every element of S.
You’re given N points, and the tolerance D.
Answer Q queries:
- Given L, R, K, find the number of integer slopes in m \in [L, R] such that at least K of the given input points belong to a line with slope m, within tolerance D.
EXPLANATION:
Let’s define \text{low}_i = Y_i - D and \text{hi}_i = Y_i+D.
These are respectively the lowest/highest y-coordinates that a line can pass through at coordinate X_i, for the i-th point to belong to it.
Now, let’s look at a line with slope m.
Claim: There exists an optimal (in the sense of maximum points belonging to it) line with slope m that passes through some \text{low}_i.
Proof
Consider an optimal line with slope m. If it doesn’t pass through some \text{low}_i, we can keep shifting it downwards till we reach one.
Notice that this shifting downwards process doesn’t change the number of points belonging to the line unless we reach either some \text{low}_i or some \text{hi}_i.
- If we reach a \text{low}_i, we’re done.
- If we reach a \text{hi}_i, then we’ve in fact managed to make a new point belong to this line; which contradicts its optimality.
Hence, we’ll always reach some \text{low}_i first, completing our proof.
Let’s attempt to use this fact.
Conditioning on both the slope and which \text{low}_i it passes through, define a function f_i, where
f_i(m) denotes the number of points belonging to the line with slope m passing through (X_i, \text{low}_i).
Using this, we can also define \displaystyle f(m) = \max_{i} f_i(m) to be the maximum number of points belonging to any line of slope m.
The important observation here is that each f_i is a step function. with \mathcal{O}(N) steps.
This is because, for fixed i and m, point (X_j, Y_j) belongs to the line if and only if
In other words, each (X_j, Y_j) adds 1 to a certain range of f_i.
Aggregating all these ‘range additions’ across all N points, we end up with a step function that has \leq 2N-1 steps.
Since each f_i is a step function, their pointwise maximum f is also a step function, though it can now have upto N\cdot (2N-1) steps.
Let’s precompute the function f, in terms of its \mathcal{O}(N^2) segments and the values on them.
This can be done in \mathcal{O}(N^2 \log N) time.
Now, let’s look at a query (L, R, K).
Relating this to the function f we have, all we need is to compute the number of L \leq x \leq R such that f(x) \geq K.
This is a (slight modification of a) rather classical problem.
Let’s compress the function f into an array, remembering the endpoints of its steps, their lengths, and the values on each one.
Then, each query requires us to find, for some range on this array, the sum of lengths across all values that are \geq K.
This is a direct modification of the “count elements \geq K in range” problem, and can be solved similarly.
A few different approaches to solve this problem are given here, though slower solutions such as sqrt decomposition/merge sort trees might TLE.
TIME COMPLEXITY
\mathcal{O}(N^2\log N + Q\log(N^2)) per testcase.
CODE:
Author's code (C++)
// optimal solution
// n<=500,q<=100000
// complexity : preprocessing : O(n*n*log(n*n)
// query : q*log(n*n)
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
class query_node
{
public:
ll pos,l,r,val,is_query;
query_node(ll pos,ll l,ll r,ll val,ll is_query):pos(pos),l(l),r(r),val(val),is_query(is_query)
{}
};
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.assign(n,0);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
void calc_max_points(vector<ll>& slopes,map<ll,vector<ll>>& add,map<ll,vector<ll>>& remove,vector<pll>& max_points)
{
multiset<ll> maxx;
for(auto& m: slopes){
for(auto& x: add[m])
maxx.insert(-x);
for(auto& x: remove[m])
maxx.erase(maxx.find(-x));
const ll val = *maxx.begin();
max_points.emplace_back(m,-val);
}
}
void solve()
{
ll n,d,q;
cin>>n>>d>>q;
vector<ll> x(n,0),y(n,0);
for(int i=0;i<n;i++)
cin>>x[i]>>y[i];
ll smallest_slope = -1ll*1e11;
ll biggest_slope = 1ll*1e11;
// vector<vector<pair<pair<ll,ll>,ll>>> max_points_point_fixed;
map<ll,vector<ll>> starts,ends;
vector<ll> total_slopes;
total_slopes.push_back(smallest_slope);
for(int i=0;i<n;i++)
{
// considering only lines which pass through [Xi,Yi-d].
// for each point [Xj,Yj] there is a range of slopes M1<=m<=M2 such that all lines
// which pass through [Xi,Yi-d] with slope M1<=m<=M2 pass within vertical distance of
// 'd' from [Xj,Yj]
set<ll> slopes;
map<ll,ll> num_line;
for(int j=0;j<n;j++)
{
if(j==i)continue;
long double m1 = (long double) (y[j]-y[i])/ (long double) (x[j]-x[i]);
long double m2 = (long double) (y[j]+d-y[i]+d)/ (long double) (x[j]-x[i]);
if(x[j]-x[i]<0)
swap(m1,m2);
ll m_min = ceil(m1);
ll m_max = floor(m2);
num_line[m_min]+=1;
num_line[m_max+1]-=1;
slopes.insert(m_min);
slopes.insert(m_max+1);
total_slopes.push_back(m_min);
total_slopes.push_back(m_max+1);
}
ll count = 1;
ll prev_count = 1;
starts[smallest_slope].push_back(1);
for(ll m: slopes)
{
count+=num_line[m];
starts[m].push_back(count);
ends[m].push_back(prev_count);
prev_count = count;
}
}
sort(total_slopes.begin(),total_slopes.end());
total_slopes.resize(unique(total_slopes.begin(),total_slopes.end()) - total_slopes.begin());
vector<pll> max_points;
calc_max_points(total_slopes,starts,ends,max_points);
ll sz = max_points.size();
// cout<<"sz = "<<max_points.size()<<'\n';
// Queries
vector<query_node> queries;
map<ll,ll> index;
for(int i=0;i<max_points.size();i++)
{
index[max_points[i].first] = i;
ll next= i+1<sz? max_points[i+1].first:1ll*1e11;
queries.emplace_back(i,max_points[i].first,next-1,max_points[i].second,0ll);
}
for(int i=0;i<q;i++)
{
int l,r,k;
cin>>l>>r>>k;
queries.emplace_back(i,l,r,k,1ll);
}
auto comp = [](query_node& x,query_node& y)
{
if(x.val==y.val)
return x.is_query>y.is_query;
return x.val<y.val;
};
sort(queries.begin(),queries.end(),comp);
vector<ll> ans(q,0);
fenwick<ll> f(sz);
set<ll> s;
auto find = [&](ll r,ll value)
{
if(s.size()==0) return 0ll;
ll ans = 0,ind = 0;
auto iter = s.upper_bound(r);
if(iter==s.begin())
return 0ll;
iter--;
ind = index[*iter];
if(ind-1>=0)ans += f.get(ind-1);
if(max_points[ind].second<value)
{
ll next= ind+1<sz? max_points[ind+1].first:1ll*1e11;
ans += min(r,next-1) - max_points[ind].first;
}
return ans;
};
for(query_node qi: queries)
{
if(qi.is_query==0)
{
f.modify(qi.pos,(qi.r - qi.l + 1));
s.insert(qi.l);
}
else
{
ans[qi.pos] = qi.r-qi.l+1;
ans[qi.pos] -= find(qi.r,qi.val)-find(qi.l-1,qi.val);
}
}
for(int i=0;i<q;i++)
cout<<ans[i]<<'\n';
}
int main()
{
#ifdef klatchu27
freopen("7.in", "r", stdin);
freopen("7.out", "w", stdout);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin>>t;
for(int ii=0;ii<t;ii++)
solve();
return 0;
}