PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Md. Mahamudur Rahaman Sajib
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Segment Tree, basic geometry, and sweep.
PROBLEM:
Given N points (x_i, y_i) in two-dimensional cartesian space, and N right isoceles triangles having (l_i, 0) to (r_i, 0) as their hypotenuse, find the number of points lying on or inside each triangle.
QUICK EXPLANATION
- We can divide the triangle (l_i, r_i) into two right triangles, each of which has it’s base at x-axis. We shall consider the left and right half of the triangle separately.
- For point (x_i, y_i) and left triangle (a, 0), ((l_i+r_i)/2, 0) and ((l_i+r_i)/2, (r_i-l_i)/2), the point lie inside the triangle if and only if x_i \leq (l_i+r_i)/2 and x_i-y_i \geq l_i.
- We can sort the points by x_i and left half of triangles by (l_i+r_i)/2, all the point with x_i \leq (l_i+r_i)/2 shall appear before this triangle. We just need to add x_i-y_i into a DS and for the triangle, we need to query the number of values in DS greater than or equal to l_i
- Similarly, for right triangle, we get conditions x_i \geq (l_i+r_i)/2 and x_i+y_i \leq r_i. We can use DS to add points x_i+y_i into DS and querying for number of points with value [(l_i+r_i)/2, r_i] after considering points with x_i \leq r_i and subtracting the number of points with values [(l_i+r_i)/2, r_i] after considering points with x_i \leq (l_i+r_i)/2
- Be careful about points lying just on the border of triangles.
EXPLANATION
Scary quick explanation, right?
Well, that was all we need to do.
Let’s split the triangles into two equal halves and try to count the number of points in each half separately and then add them while taking care not to include any point twice.
Refer the following images for a rough idea (Please ignore size, my first time with graphing tools, also suggest good graphing tools please).
Let’s consider only left triangles for now. It is each to see that coordinates of the left triangle are of form (a_i, 0), (b_i, 0) and (b_i, b_i-a_i)
Considering the equation of each side of the triangle or even by observation, we can easily deduce that a point (x_i, y_i) lies in this triangle if x_i \leq b_i, y_i \geq 0 and x_i - y_i \geq a_i.
Since all points have y_i \geq 0, we can ignore that condition.
Let’s order the points by x_i and left triangles by b_i in increasing order. Hence, some prefix of the point shall satisfy condition x_i \leq b_i.
The only condition left is the condition x_i - y_i \geq a_i. Let’s assume a data structure supporting insertion of integer values and querying the number of values within a range.
We can use a segment tree to add values x_i-y_i for each point and whenever we get a left triangle, we query for the number of values in range [a_i, b_i].
Hence, we have counted the number of points in the left triangle.
For right triangle, we have two approaches, one is to replace all x coordinates with 10^6-x and apply the idea for the left triangle.
The other one is a bit different. See the second image.
The coordinates of right triangle is of form (a_i, 0), (a_i, (b_i-a_i)) and (b_i, 0). We can derive conditions x_i \geq a_i, y_i \geq 0 and x_i+y_i \leq b_i
Once again we can use the segment tree, adding values x_i+y_i to the segment tree. After considering all points with x_i \leq b_i, we can query for number of values in range [a_i, b_i]. But this shall also include point P as shown in the image. We can exclude that by subtracting the number of values in range [a_i, b_i] after considering all points with x_i \leq a_i
Tips For such problems
- It is helpful to scale the whole grid by a factor of 2, to avoid dealing with half values.
- I know the above editorial is far longer and could be shorter, but Just as we derived conditions here, we can virtually derive the condition for any geometrical shapes.
- Try using test cases with points on the border, points close to the border for debugging.
TIME COMPLEXITY
The time complexity is $O((N+Q)*log(N+Q)) per test case.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <cstring>
#include <iostream>
#define pie acos(-1)
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sl(a) scanf("%lld",&a)
#define sll(a,b) scanf("%lld %lld",&a,&b)
#define slll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define ss(st) scanf("%s",st)
#define sch(ch) scanf("%ch",&ch)
#define ps(a) printf("%s",a)
#define newLine() printf("\n")
#define pi(a) printf("%d",a)
#define pii(a,b) printf("%d %d",a,b)
#define piii(a,b,c) printf("%d %d %d",a,b,c)
#define pl(a) printf("%lld",a)
#define pll(a,b) printf("%lld %lld",a,b)
#define plll(a,b,c) printf("%lld %lld %lld",a,b,c)
#define pd(a) printf("%lf",a)
#define pdd(a,b) printf("%lf %lf",a,b)
#define pddd(a,b,c) printf("%lf %lf %lf",a,b,c)
#define pch(c) printf("%ch",c)
#define debug1(str,a) printf("%s=%d\n",str,a)
#define debug2(str1,str2,a,b) printf("%s=%d %s=%d\n",str1,a,str2,b)
#define debug3(str1,str2,str3,a,b,c) printf("%s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c)
#define debug4(str1,str2,str3,str4,a,b,c,d) printf("%s=%d %s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c,str4,d)
#define for0(i,n) for(i=0;i<n;i++)
#define for1(i,n) for(i=1;i<=n;i++)
#define forab(i,a,b) for(i=a;i<=b;i++)
#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define nl puts("")
#define sd(a) scanf("%lf",&a)
#define sdd(a,b) scanf("%lf %lf",&a,&b)
#define sddd(a,b,c) scanf("%lf %lf %lf",&a,&b,&c)
#define sp printf(" ")
#define ll long long int
#define ull unsigned long long int
#define MOD 1000000007
#define mpr make_pair
#define pub(x) push_back(x)
#define pob(x) pop_back(x)
#define mem(ara,value) memset(ara,value,sizeof(ara))
#define INF INT_MAX
#define eps 1e-9
#define checkbit(n, pos) (n & (1<<pos))
#define setbit(n, pos) (n (1<<pos))
#define para(i,a,b,ara)\
for(i=a;i<=b;i++){\
if(i!=0){printf(" ");}\
cout<<ara[i];\
}\
printf("\n");
#define pvec(i,vec)\
for(i=0;i<vec.size();i++){\
if(i!=0){printf(" ");}\
cout<<vec[i];\
}\
printf("\n");
#define ppara(i,j,n,m,ara)\
for(i=0;i<n;i++){\
for(j=0;j<m;j++){\
if(j!=0){printf(" ");}\
cout<<ara[i][j];\
}\
printf("\n");\
}
#define ppstructara(i,j,n,m,ara)\
for(i=0;i<n;i++){\
printf("%d:\n",i);\
for(j=0;j<m;j++){\
cout<<ara[i][j];printf("\n");\
}\
}
#define ppvec(i,j,n,vec)\
for(i=0;i<n;i++){\
printf("%d:",i);\
for(j=0;j<vec[i].size();j++){\
if(j!=0){printf(" ");}\
cout<<vec[i][j];\
}\
printf("\n");\
}
#define ppstructvec(i,j,n,vec)\
for(i=0;i<n;i++){\
printf("%d:",i);\
for(j=0;j<vec[i].size();j++){\
cout<<vec[i][j];printf("\n");\
}\
}
#define sara(i,a,b,ara)\
for(i=a;i<=b;i++){\
scanf("%d",&ara[i]);\
}
#define pstructara(i,a,b,ara)\
for(i=a;i<=b;i++){\
cout<<ara[i];nl;\
}
#define pstructvec(i,vec)\
for(i=0;i<vec.size();i++){\
cout<<vec[i];nl;\
}
#define pstructstl(stl,x)\
for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
x=*it;\
cout<<x;nl;\
}\
nl;
#define pstl(stl)\
for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
if(it!=stl.begin()){sp;}\
pi(*it);\
}\
nl;
#define ppairvec(i,vec)\
for(i=0;i<vec.size();i++){\
cout<<vec[i].first;sp;cout<<vec[i].second;printf("\n");\
}
#define ppairara(i,a,b,ara)\
for(i=a;i<=b;i++){\
cout<<ara[i].first;sp;cout<<ara[i].second;printf("\n");\
}
#define pppairvec(i,j,n,vec)\
for(i=0;i<n;i++){\
printf("%d:\n",i);\
for(j=0;j<vec[i].size();j++){\
cout<<vec[i][j].first;sp;cout<<vec[i][j].second;nl;\
}\
}
#define pppairara(i,j,n,m,ara)\
for(i=0;i<n;i++){\
printf("%d:\n",i);\
for(j=0;j<m;j++){\
cout<<ara[i][j].first;printf(" ");cout<<ara[i][j].second;nl;\
}\
}
#define SZ 2 * 100010
#define xx first
#define yy second
using namespace std;
//using namespace __gnu_pbds;
//bool status[100010];
//vector <int> prime;
//void siv(){
// int N = 100005, i, j; prime.clear();
// int sq = sqrt(N);
// for(i = 4; i <= N; i += 2){ status[i] = true; }
// for(i = 3; i <= sq; i+= 2){
// if(status[i] == false){
// for(j = i * i; j <= N; j += i){ status[j] = true; }
// }
// }
// status[1] = true;
// for1(i, N){ if(!status[i]){ prime.pub(i); } }
//}
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
//std::mt19937 mt(seed);
inline int add(int _a, int _b){
if(_a < 0){ _a += MOD; }
if(_b < 0){ _b += MOD; }
if(_a + _b >= MOD){ return _a + _b - MOD; }
return _a + _b;
}
inline int mul(int _a, int _b){
if(_a < 0){ _a += MOD; }
if(_b < 0){ _b += MOD; }
return ((ll)((ll)_a * (ll)_b)) % MOD;
}
const int N = 1e6;
int n, f[2 * N + 5], m, sol[N + 5];
pair < pair <int, int >, int> ara[N + 5], tri[N + 5];
void update(int p, int v){
while(p <= 2 * N + 5) f[p] += v, p += (p & (-p));
}
int query(int p){
int ret = 0;
while(p) ret += f[p], p ^= (p & (-p));
return ret;
}
void solve(){
int i, j;
ll ans = 0;
sort(ara, ara + n);
sort(tri, tri + m);
for(i = m - 1, j = n - 1; i >= 0; --i){
for(; j >= 0 && ara[j].xx.xx >= tri[i].xx.xx; --j) update(ara[j].xx.yy + 1, +1);
sol[tri[i].yy] = query(tri[i].xx.yy + 1);
}
for(++j; j < n; ++j) update(ara[j].xx.yy + 1, -1);
for0(i, m){
if(i) sp;
pi(sol[i]);
} nl;
}
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt", "w", stdout);
// freopen("0.in", "r", stdin);
// freopen("0.out", "w", stdout);
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
int cs, ts;
si(ts);
for0(cs, ts){
int i, j, x, y;
sii(n, m);
for0(i, n){
sii(x, y);
assert(x >= 0 && y >= 0 && x <= N && y <= N);
ara[i] = mpr(mpr(x - y, x + y), i);
}
for0(i, m){
sii(tri[i].xx.xx, tri[i].xx.yy);
assert(tri[i].xx.xx >= 0 && tri[i].xx.yy >= 0 && tri[i].xx.xx <= N && tri[i].xx.yy <= N);
tri[i].yy = i;
}
solve();
}
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
pii pt[1234567];
int bit[4323456];
int offset;
int MAXN=4323456;
int update(int pos,int val){
pos+=offset;
while(pos<MAXN){
bit[pos]+=val;
pos+=pos&(-pos);
}
return 0;
}
int query(int pos){
pos+=offset;
int ans=0;
while(pos){
ans+=bit[pos];
pos-=pos&(-pos);
}
return ans;
}
int ans[1234567],l[1234567],r[1234567];
signed main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t=1;
cin>>t;
while(t--){
int n,q;
cin>>n>>q;
int i;
rep(i,n){
cin>>pt[i].ff>>pt[i].ss;
pt[i].ff*=2;
pt[i].ss*=2;
}
sort(pt,pt+n);
// forward step take the mid line also.
vii aft,bef;
int mid;
rep(i,q){
cin>>l[i]>>r[i];
l[i]*=2;
r[i]*=2;
mid=(l[i]+r[i])/2;
aft.pb(mp(mid,i));
bef.pb(mp(mid,i));
ans[i]=0;
}
sort(all(bef));
sort(all(aft));
int j=0,ind;
offset=2234567;
pt[n].ff=inf;
rep(i,n){
while(j<aft.size() && aft[j].ff<pt[i].ff){
ind=aft[j].ss;
ans[ind]+=i-query(l[ind]-1);
j++;
}
update(pt[i].ff-pt[i].ss,1);
//cout<<pt[i].ff<<" lol "<<pt[i].ff-pt[i].ss<<endl;
}
while(j<aft.size()){
ind=aft[j].ss;
ans[ind]+=i-query(l[ind]-1);
j++;
}
rep(i,n){
update(pt[i].ff-pt[i].ss,-1);
}
j=bef.size();
j--;
offset=2;
fd(i,n-1,0){
while(j>=0 && bef[j].ff>=pt[i].ff){
ind = bef[j].ss;
ans[ind]+=query(r[ind]);
j--;
}
update(pt[i].ff+pt[i].ss,1);
}
while(j>=0){
ind = bef[j].ss;
ans[ind]+=query(r[ind]);
j--;
}
rep(i,n){
update(pt[i].ff+pt[i].ss,-1);
}
rep(i,q){
cout<<ans[i]<<" ";
}
cout<<endl;
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
