Polygon & Circles
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef recently fell in love with geometry problems. Today, his friend John asks him to help. John is a student of Kiev National University and he is currently studying a beautiful subject called "Analytic Geometry". This subject is well known for its hard problems. John asked the following question to Chef, but Chef could not solve it and asked your help in solving this.
You are given a convex polygon and M circles in 2-D plane. Find out the area of the parts of polygon which are covered by some circle. In other words, you have to output area of parts which lie in the polygon and in at least one of the circles.
- There is only one test case per test file.
- The first line of test case contains a single integer M denoting number of circles.
- Each of the next M lines contains three integers x, y, r, where (x, y) denotes the x and y coordinates respectively of the center of the circle and r denotes the radius of each circle.
- Next line contains an integer N denoting number of vertices in given polygon.
- Each of the next N lines contains two integer x, y denoting the coordinate of a vertex of polygon.
Output a single line denoting the answer of the problem. Your answer will be considered correct if it has an absolute error less than 10-2.
- 1 ≤ N ≤ 50
- -10^4 ≤ x[i],y[i] ≤ 10^4 (coordinates of polygon)
- 1 ≤ M ≤ 50
- -10^4 ≤ x, y ≤ 10^4
- 0 < r ≤ 10^4
- Subtask #1 [30 points]: 1 ≤ N, M ≤ 5
- Subtask #2 [70 points]: 1 ≤ N, M ≤ 50
Input: 2 0 0 11 10 10 1 4 0 0 50 50 100 50 100 0 Output: 49.087385212341
Example case 1. Two circles that are not intersecting each other.
|Tags||furko, greens-theorem, hard, march16|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.