Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2564
The Magic Wheel

Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge

The great magician Zahruman is going to create the great artefact - the magic wheel. The magic wheel is a circular cylinder with radius r and height h. Along each of the two circular bases of the wheel there are n special lugs. Also there are n small loops located along a circle surronding the cylinder in the middle.

To turn the wheel into the magic artefact, one needs to connect pairs of lugs on the base circles by magic threads. Each lug must be connected to exactly one lug from the other circle. Each thread in turn must pass through one of the loops of the central circle. There must be exactly one thread passing through each of the loops.

Since magic thread is a rather expensive thing, Zahruman wants to use as little of it as possible. So he wants to know what is the minimal possible length of the n threads. And of course, to construct the wheel with the thread of that length he needs to know which pairs of lugs should be connected, and which loop should each thread pass through. Each thread must run along the lateral face of a cylinder, it is not allowed to run thread along cylinder base.


There are several test cases. The first line of each test case contains 3 integers n , r and h(1 <= n <= 1000, 1 <= r, h <= 100). The second describes lugs on the top base circle of the cylinder, it contains n real numbers - polar angles of the lugs in radians. No two lugs coincide. The third line describes loops on the center circle in the same format. The fourth line describes lugs on the bottom base circle. All polar angles are in range [-2Pi, 2Pi] and measured from some common direction orthogonal to the cylinder axis. The input is terminaled by EOF.


For each test case,the output should be excatly n+1 lines: On the first line of ecah test case print the total length of all magic threads. After that output n lines, each with three integer numbers: ai, bi and ci - the number of the lug on the top base circle, the number of the loop on the center circle, and the number of the lug on the bottom base circle to use for the i-th thread. Your answer must be accurate up to 4 place after decimal point.

Sample Input
3 10 4
0 1.57079632679489662 3.14159265358979324
-1.57079632679489662 0 3.14159265358979324
3.14159265358979324 0 1.57079632679489662
Sample Output
1 1 2
2 2 3
3 3 1

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4
Submit    Status