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 2D 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.
Input
 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
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}.
Constraints
 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
Subtasks
 Subtask #1 [30 points]: 1 ≤ N, M ≤ 5
 Subtask #2 [70 points]: 1 ≤ N, M ≤ 50
Example
Input: 2 0 0 11 10 10 1 4 0 0 50 50 100 50 100 0 Output: 49.087385212341
Explanation
Example case 1. Two circles that are not intersecting each other.
Author:  furko 
Tester:  kevinsogo 
Editorial  http://discuss.codechef.com/problems/CHEFPC 
Tags  furko, greenstheorem, hard, march16 
Date Added:  3042015 
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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions