# TRIQRY - Editorial

Setter: Md. Mahamudur Rahaman Sajib
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

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); } }
//}
//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.

6 Likes

I tried solving it by finding points that satisfy l+y-x<=0 && r-x-y>=0 still not able to find why this method fails.(Points that lie on same side of origin to side side from r and opposite side of origin to the side from l ).

2 Likes

same here bro! i also use condition x-y>=l and in all those points with using bit i try to find all those point with x-y<=r,but still getting wrong ans

1 Like

It will time out right?

1 Like

Sort on one inequalty say x-y and use BIT to handle other inequality

1 Like

it will Submission

2 Likes

Yes that would have worked for 50pts I think, since height remains constant. You can eliminate all the points above the height of the triangle and do this

Small fix: the closing dollar sign is missing on the time complexity

Thanks for the tip of multiplying all coordinates by 2! (not doing that made my sol so much more complicated)

3 Likes

Same approach with BIT was TLEing

Intersection of two the regions should area of the triangle and its extended sector below y axis so I was hoping for a complete solution through this method rather than a subtask.

If this is what you mean, you would be missing out on points in area ‘d’.

That is why I said one could have got 50 on this by eliminating points above the triangle height

D won’t satisfy r-y-x>=0

@taran_1407 can’t this be solved using mo’s algorithm?
sort all the points according to x value
for any query l,r we can first determine the index in arrays such that L=i and R=j and a[L].x_value >=l and a[R].x_value<=r using binary search.
After modifying the queries we can use mo’s I think, where for each modified query we need to find the number of points in the interval L-R such that the slope is ±1 from original l and r.

You will be getting a+b and a+c by using line equations right?

yes

How do u plan to find a?

Rotating the axes 90 degrees clockwise and scaling the coordinates by 2*sqrt(2) makes the coding part much easier.

The equation of left side of triangle will be x-y = l and right side will be x+y = r.
So sorted all points on x-y. Also sorted all queries. Now starting from the right most queries, I put all points with x-y>=l in ordered_set. Then find the number of points having x+y less than r+1 in ordered_set.

Why does this solution get WA?

You can’t find a by

(a+b)+(a+c) - n

Because that’s what I tried to do

Sort on y-x and use binary search to get all solutions to l+y-x<=0 then for this range use BIT to find solutions for r-x-y>=0 .Isse Intersection aa jana chahiye tha pata nhi kya gadbad ho ri hai