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?

Input Format

There are 10 test cases path1.in ~ 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 x_i and y_i, indicating that the i-th point has coordinates (x_i, y_i).
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.

Output Format

The output should consist of one line with a single integer, the total area of the regions traced over by little Z's brush.

Sample Input

2
1 1
1 2
1
1 2
1
0.00001 0.001 0.1 1

Sample Output

5.1415927

Explanation

The scenario in the sample is depicted in the figure below.

Scoring

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.

All Submissions
Best Solutions

Point Value: 50 (partial)
Time Limit: 60.00s
Memory Limit: 256M
Added: Aug 04, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

There are a few problems from the recent NOI's I've been translating which were actually designed to be output-only tasks (i.e. competitors would submit 10 output files that they've generated over the entire contest period, which lasts several hours).

These also currently include the following:

NOI '05 - Little H's Party: [url]http://wcipeg.com/problem/noi05p5[/url]
NOI '06 - The Clever Tour Guide: [url]http://wcipeg.com/problem/noi06p5[/url]
NOI '07 - Surrounding Battalions: [url]http://wcipeg.com/problem/noi07p3[/url]
NOI '08 - Tournament Matching: [url]http://wcipeg.com/problem/noi08p6[/url]

However, you may have noticed that their formats here on the judge do [i]not[/i] support TEXT submissions (although the inputs are openly available for you to study). Here's my reasoning:
[list][*]Most of these problems have solutions that can pass within a reasonable time limit. This format should hopefully encourage users to submit actual code that fully solves the problems with minimal "hacks". I feel that this is much more well-formed than just having pages of identical or nearly-identical output files in the user submissions list. Note that this PARTICULAR problem is an exception, because it really is insane (admin's solution only passes the last case in ~11 days :neutral:).

[*]Sometimes you may feel like cheap hacks are necessary. Well, they probably are! Don't be scared to make sketchy observations and/or exploit the test data, as this was most certainly intended during the original contest.

[*]If you cannot possibly think of a "full solution" that solves the set of ALL possible inputs, feel free to go for "generator solutions" where you only generate data that solves the specific cases. If your solution is based on randomization, I recommend finding just the right seed on your own computer which gets the right answer and seeding the randomizer in your submission.

[*]The last resort when you just don't think the above methods are appropriate, is to resort to handcrafted and/or hardcoded solutions. Most of these output formats are really short, so you'll be able to fit the answers comfortably in your source. But if the output is long, I suggest compressing your output into strings before decompressing it and printing. Of course, hardcoding is lame, but hey, that's life sometimes.
[/list]These are only some basic suggestions so people don't get confused or think that a problem is impossible. You can definitely ignore them and just hardcode all the things, but where's the fun in that?