×

Medium

# Pre-requisites:

line-sweep, rank-query DS

# Problem:

Given N points (Xi, Yi), and Q queries (x, y, d), find for each query how many of the N points lie within or on the boundary of the triangle formed by the triangle A(x+d, y), B(x,y), C(x,y+d).

# Explanation:

This problem is solved by offline processing of the queries and using a line-sweep. Unlike most line-sweep problems, where you would sweep a (vertical) line across the X-axis (or a horizontal line across the Y-axis), and keep an active set etc, in this problem, you sweep a line of the form "x+y=c" across the plane. (Note that the slope of the hypotenuse of our query-triangle is parallel to such a sweep-line and hence the motivation for such a choice).

In the figure shown, we want to find the number of points in or within the boundary of L2, B and G. If we are processing lattice points in the plane in order of sweep-line, and have so far seen points below L2, we just need to remove from this set of seen points, the ones that are below G or to the left of B.

This suggests that we have an active set of "seen points", wherein at time T, their X+Y <= T (i.e. T defines our sweep-line). From this set of seen points, we want to remove those whose X <= x, or whose Y <= y. If we store the seen points in 2 Binary Indexed Trees (BIT): one for their X coordinate, one for their Y coordinate, and query for how many points <= x, or <= y, then using principle of inclusion-exclusion, we get that the required answer = Total seen points - num(points left of B) - num(points below G) + num(points left of B and below G).

How do we find num(points left of B and below G)?
The answer lies in the line L1. When our sweep-line was at L1, we have: Total number of points seen so far = points either left of B or below G. Again by Inclusion-Exclusion, we have Total points seen so far = num(points left of B) + num(points below G) - num(points left of B and below G). From this, we can calculate num(points left of B and below G).

Thus, our algorithm is as follows:
For each of the N lattice points (X, Y), associate an event "Add (X,Y) to active set at time point X+Y".
For every query (x, y, d), associate 2 events. Event 1 is: "Find num(points having X<=x and Y<=y) at time point x+y".
Event 2 is: "Answer required query at time point x+y+d".
Lets call the first kind of event as "Add point" event, the second kind of event as "L1-type" event, and the third kind as "L2-type" event.

Finally, care has to be taken to ensure that we include the boundary of our triangle formed by B, G, L2. This is done by breaking ties of time-point in the manner of L1-type event comes before any Add-point event which comes before any L2-type event.

# Setter's Solution:

Can be found here

# Tester's Solution:

Can be found here

This question is marked "community wiki".

973568379
accept rate: 14%

Setter nice and clear solution!

(14 Feb '13, 18:20)

I have a problem here: -->"How do we find num(points left of B and below G)? The answer lies in the line L1. When our sweep-line was at L1, we have: Total number of points seen so far = points either left of B or below G."<-- I think if L1 sweep means all the points below this line in the diagram then it is "not" equal to the "points on the left of B or below G" because there can be some point b/w L2 and L1 and on the left of B which are not covered by L1 sweep. same for b/w L2 and L1 and below G. please clarify. Please also clarify the definition of line-sweep.

(23 Feb '13, 12:46)
1

got it. :) For this part of problem (refer above comment), it is a completely new BIT which is calculated from points and queries sorted by their x coordinate. see Setter's solution for clarification.

(23 Feb '13, 13:02)

 2 Can't this problem also be solved by doing an orthogonal range search in 3 dimensions (between (x, y, x+y) and (x+d, y+d, x+y+d)) using range trees or kd trees? Something like this http://www.codechef.com/viewsolution/1809831 (kd-tree, TLE, Complexity is q*(n^2/3)) Range trees with fractional cascading could solve this in O(q*((log(n))^2)) answered 13 Feb '13, 07:06 850●2●6●14 accept rate: 21%
 1 I tried to solve this in online mode: i stored count of points on different lines parallel to x+y=0 on query of (x,y,d) we can find points to the left of B and below G (as used in editorial) by using two segment trees. each segment tree is built with (level,x) and (level,y) correspondence (level is line no. with respect to x+y=0) i couldn't get rid of RTE in my submission but is this method good enough for this problem...?? answered 12 Feb '13, 21:47 1.1k●13●22●29 accept rate: 0% @code_master01 I tried same logic too I am getting RTE too :(... (13 Feb '13, 12:11)
 1 Is there any other simple to implement data structure for rank-query other than balanced BST if the range of value is 10^9 ? answered 14 Feb '13, 18:56 105●6 accept rate: 0% 2 One generally maps your range of 10^9 values to O(10^5) actual values. (Use a STL map or set or something). The mapping should only preserve ordering of elements. For example, if your input (into your BST) was 5, 10, 10^7, then first make the mapping  5 -> 1 10 -> 2 10^7 -> 3  and use just these mapped values in your BIT. (17 Feb '13, 03:51) I thought of this . but suppose we want to do online processing of queries . (20 Feb '13, 20:56)
 0 Could somebody please tell me what do we mean by offline processing of points? And also why was I getting a runtime error in my code http://www.codechef.com/viewsolution/1802839 answered 12 Feb '13, 23:12 525●23●35●50 accept rate: 0% 1 offline mode means that you "don't" calculate your answer of every input query separately but either you do some preprocesing before taking input or you take all the input and find answer to the all queries at the same time. [here same time means like you are going though the input queries and finding "half" answer to some queries and then coming back again and again] (23 Feb '13, 12:35)
 0 answered 12 Feb '13, 23:25 8.7k●19●48●98 accept rate: 9% Your solution has complexity O(N * Q). Obviously it will get TLE. Did you ever try to run your solution with N=3e5 and Q=2e5? (13 Feb '13, 00:58) How to run it with N=3e5 and Q=2e5? (14 Feb '13, 17:39) I meant how to manually create such a test file. (14 Feb '13, 17:54) This is the code for manually creating a test file #include #include int main() {printf("300000 200000\n"); for(int i=1;i<=500;i++) {for(int j=1;j<=600;j++) printf("%d %d\n",i,j);} for(int i=1;i<=200000;i++) printf("%d %d %d\n",i,i,i); return 0; }  (14 Feb '13, 21:19) then direct the output of this program to the input of ur program. where input.txt is text file generated from the above code. ./a.out
 0 I do not get this part in the setter's solution, please help: int comp_pt(pt A,pt B) // For sorting points by their diagonal { return A.x+A.y d. So having all the points sorted w.r.t "x+y", gives a quick way to eliminate points. (16 Feb '13, 22:43) thank you. (16 Feb '13, 23:20)
 0 very nice editorial :) answered 24 Feb '13, 10:34 10●1●2●7 accept rate: 0%
 0 Could somebody explain me the update and read functions in the tester's solution? I couldn't get this line void update(int idx,int val,int x) { while (idx <= maxn) tree[x][idx]=(tree[x][idx]+val),idx += (idx & -idx); } What is the meaning of idx&-idx? answered 25 Jun '13, 15:42 525●23●35●50 accept rate: 0%
 0 Could somebody help me with the editorial? Somebody explain me the update and read functions in the tester's solution? I couldn't get this line void update(int idx,int val,int x) { while (idx <= maxn) tree[x][idx]=(tree[x][idx]+val),idx += (idx & -idx); } What is the meaning of idx&-idx? answered 25 Jun '13, 23:28 525●23●35●50 accept rate: 0% 1 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees (25 Jun '13, 23:43) its idx&-idx the bitwise AND operation between idx and its negation (25 Jun '13, 23:43) Thanx @sparshgunner12. I finally understood whats happening. (26 Jun '13, 19:39)
 0 Excellent editorial and tester's solution. answered 26 Jun '13, 19:39 525●23●35●50 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,682
×2,595
×78
×13
×3

question asked: 12 Feb '13, 18:20

question was seen: 7,736 times

last updated: 26 Jun '13, 19:39