### 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 `path`

will have `x`.in`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`, indicating that the

_{i}`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)

Alexon Aug 04, 2014 - 2:11:02 pm UTC Rationale behind modified output-only problemsThese also currently include the following:

NOI '05 - Little H's Party: http://wcipeg.com/problem/noi05p5

NOI '06 - The Clever Tour Guide: http://wcipeg.com/problem/noi06p5

NOI '07 - Surrounding Battalions: http://wcipeg.com/problem/noi07p3

NOI '08 - Tournament Matching: http://wcipeg.com/problem/noi08p6

However, you may have noticed that their formats here on the judge do not support TEXT submissions (although the inputs are openly available for you to study). Here's my reasoning:

- 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 ).

- 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.

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?