National Olympiad in Informatics, China, 2009
Day 2, Problem 3 - Tracing
Little Z has been fond of mathematics ever since he was little. Being the smart fella he is, little Z really enjoys examining little problems in mathematics.
One day, little Z selected n points on a sheet of paper and connected all of them pair-by-pair, creating a total of n(n − 1)/2 line segments. Since the pencil is very sharp, we can consider the thickness of the line segments to be effectively 0.
Staring at these line segments, little Z fell into deep thought. He believed that a certain subset of these segments is of particular importance, and should be further examined. Thus, little Z took out his brush to retrace them. Applying his brush to the paper will produce a circle of radius r. To trace a line segment, the tip of the brush (i.e. the center of the circle) starts at one endpoint, moving along the entire segment until it finally reaches the other endpoint. The figure below depicts a scenario with 4 points, where one line segment has already been traced.
Now, little Z would really like to know how large the total area of the traced region is. Can you help him answer this question?
There are 10 test cases
path10.in that will be given to your program (through standard input). They can be downloaded here for you to study: path.zip
Line 1 of input contains two positive integers T and n, respectively representing the test case number (between 1 and 10; the test case
pathx.in will have T = x) and the number of points on the paper.
For lines 2 to n + 1, line i + 1 will contain two real numbers xi and yi, indicating that the i-th point has coordinates (xi, yi).
Line n + 2 contains one positive integer m, representing the number of line segments that little Z considers particularly important.
For lines n + 3 to n + m + 2, each line will contain two positive integers a and b to describe a line segment. Point a and point b will be its two endpoints.
Line n + m + 3 will contain a single real number r, representing the radius of circle created by applying the brush to the paper.
Line n + m + 4 will contain 4 real numbers p1, p2, p3, and p4, the parameters used for grading.
The output should consist of one line with a single integer, the total area of the regions traced over by little Z's brush.
2 1 1 1 2 1 1 2 1 0.00001 0.001 0.1 1
The scenario in the sample is depicted in the figure below.
Each test case will be graded independently.
The 4 grading parameters p1, p2, p3, and p4 (p1 < p2 < p3 < p4) are provided for you in the input.
Your score for each test case will be determined as follows:
If your answer and the correct answer differ by no more than p1, then you will receive full points.
Otherwise, if your answer and the correct answer differ by no more than p2, then you will receive 70% of points.
Otherwise, if your answer and the correct answer differ by no more than p3, then you will receive 40% of points.
Otherwise, if your answer and the correct answer differ by no more than p4, then you will receive 10% of points.
Otherwise, you will be given a score of 0.
Point Value: 50 (partial)
Time Limit: 60.00s
Memory Limit: 256M
Added: Aug 04, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3