This page is still under construction.

Parts of this page are still being built. What you see may change.

Heavenly Jewels

Time limit2sMemory limit512 MB

Summary
Given three fixed points in a 10000 by 10000 square, find the area where IC's point is the last-nearest among the three, divided by the square's area.
Level

Medium7 of 10

Topics
Geometry, Math, Implementation
Solved
No attempts yet

Problem

There is an island whose shape is a perfect square. On this island live three inhabitants named IC, PC, and ACM. Every day, one jewel is dropped from the sky. Just as the jewel touches the ground, IC, PC, and ACM leave their houses simultaneously, run at the same speed, and the person who first touches the jewel gets it. Hence, the person whose house is nearest to the location of the jewel is the winner of that day.

They always quarrel with each other, so their houses are located at distinct places. The locations of their houses are fixed. This jewel falls at a random point on the island, that is, all points on the island have equal chance.

When there are two or more persons whose houses are simultaneously nearest, the last person in the order of

IC, PC, ACM

obtains the jewel. Our interest is to know the probability for IC to get the jewel under this situation.

Input

The input describes one problem instance per line. Each line contains the x- and y-coordinates of IC's home, those of PC's, and those of ACM's in this order. Note that the houses of IC, PC, and ACM are located at distinct places. The end of the input is indicated by a line with six zeros.

The coordinates of the whole island are given by (0, 10000)(0, 10000) and coordinates of houses are given in integer numbers between 1 and 9999; inclusive. It should be noted that the locations of the jewels are arbitrary places on the island and their coordinate values are not necessarily integers.

Output

For each input line, your program should output its sequence number starting from 1, and the probability for the instance. The computed probability values should have errors less than 10-5.

The sequence number and the probability should be printed on the same line. The two numbers should be separated by a space.

Examples1

  1. Example 1

    Input
    2000 2000 8000 8000 9000 9500
2500 2500 7500 2500 2500 7500
0 0 0 0 0 0
    Expected output
    1 0.50000
2 0.25000