The New Restaurant
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef decided to open a new restaurant in the town. The town already has N restaurants, each of which operates in an area of circular shape with its center at xi, yi and radius ri. For any point, there is at most one restaurant operating there.
Chef wants to build his restaurant in a strategic place. That's why he asks you some questions - find the total area covered by restaurants in the rectangle defined by the points x1, y1, x2, y2 where (x1, y1) is the lower left corner and (x2, y2) is the upper right corner. Chef is not that good in answering these questions, so he asked you to help him in this.
There is a single test case.
The first line of input contains two integers N, Q, denoting number of restaurants and number of questions Chef asks.
Each of the next N lines contains three space separated integers x, y, r denoting x and y coordinate of center, and the radius of the restaurant, respectively.
Each of the next Q lines contains four space separated integers x1, y1, x2, y2 denoting a question as defined in the statement.
Output Q lines, the i-th line contains the total area covered by restaurants in the rectangle defined by the i-th query. The answer will be considered correct if its absolute or relative error does not exceed 10-6
- 1 ≤ N ≤ 50 000
- 1 ≤ Q ≤ 100 000
- 0 ≤ xi, yi ≤ 50 000
- 1 ≤ ri ≤ 50
- 0 ≤ xi1 < xi2 ≤ 50 000
- 0 ≤ yi1 < yi2 ≤ 50 000
- No two circles touch or intersect each other.
Subtask #1 (10 pts)
- N = 1
Subtask #2 (10 pts)
- 1 ≤ N, Q ≤ 1000
- 0 ≤ xi, yi ≤ 1000
- 0 ≤ xi1 < xi2 ≤ 1000
- 0 ≤ yi1 < yi2 ≤ 1000
Subtask #3 (10 pts)
- 1 ≤ N, Q ≤ 1000
Subtask #4 (20 pts)
- Original constraints with ri = 1
Subtask #5 (50 pts)
- Original constraints
Input: 2 4 5 5 2 2 2 1 2 2 5 5 1 1 7 7 2 3 8 4 1 3 2 4 Output: 3.926990816987241 15.707963267948966 2.456739397217513 0.000000000000000
|Tags||amrmahmoud, medium-hard, sept16|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.