Sample Input and Output

Задача 5. Dome of Circus

Input file: dome.in

Output file: dome.out

Time Limit: 1 second

Memory Limit: 64M byte

A travelling circus faces a tough challenge in designing the dome for its performances. The circus has a number of shows that happen above the stage in the air under the dome. Various rigs, supports, and anchors must be installed over the stage, but under the dome. The dome itself must rise above the center of the stage and has a conical shape. The space under the dome must be air-conditioned, so the goal is to design the dome that contains minimal volume.

You are given a set of n points in the space; (x_i, y_i, z_i) for 1 · i · n are the coordinates of the points in the air above the stage that must be covered by the dome. The ground is denoted by the plane z = 0, with positive z coordinates going up. The center of the stage is on the ground at the point (0; 0; 0). The tip of the dome must be located at some point with coordinates (0; 0; h) with h > 0. The dome must have a conical shape that touches the ground at the circle with the center in the point (0; 0; 0) and with the radius of r. The dome must contain or touch all the n given points. The dome must have the minimal volume, given the above constraints.

Input

The first line of the input file contains a single integer number n (1 ≤· n ≤10 000) - the number of points under the dome. The following n lines describe points with three floating point numbers x_i, y_i, and z_i per line - the coordinates of i-th point. All coordinates do not exceed 1000 by their absolute value and have at most 2 digits after decimal point. All z_i are positive. There is at least one point with non-zero x_i or y_i.

Output

Write to the output file a single line with two floating point numbers h and r - the height and the base radius of the dome. The numbers must be precise up to 3 digits after decimal point.

Sample input and output

Задача 6. Mothy

Input file: mothy.in

Output file: mothy.out

Time Limit: 1 second

Memory Limit: 64M byte

Mothy is a small moth. Mothy and his mother are placed on a very old pair of jeans. Because the jeans are very old they are covered with patches. Sometimes the patches overlap each other. Every patch is a convex polygon and is made by some material different from cotton. Mothy wants to go to his mother in the fastest possible way. He cannot move without eating and because of his age he cannot eat anything except jeans and cotton thread. Despite his age Mothy is very intelligent, he can move following precise coordinates but he is unable to compute them. Write a program that calculates the length of the minimal path from the position of Mothy to the position of his mother. Mothy must be able to pass through this path. Consider that the pair of old jeans is placed on a plane surface and is big enough. Mothy can move only at the surface of the jeans because he is not big enough to penetrate through them.

Because Mothy is so small he should be considered as a point. Mothy also can move on the edges of any of the patches because they are sewed with cotton threads. Mothy can move on common edges but cannot be on top of any patch.

Input

Input starts with number N of patches, and four integer numbers – the coordinates X and Y of Mothy’s position and coordinates U and V of his mother’s position, separated by white spaces (-10000 ≤ X, Y, U, V ≤ 10000). Each patch is described on a separate line starting with the number of vertices and followed by a pair of integer coordinates (-10000 ≤ X_i, Y_i ≤ 10000) for each of the vertices of the patch, separated by white spaces. The total number of vertices of polygons will not exceed 300.

Output

Program has to output on a separate line the length of the shortest path between Mothy and his mother. The result should be rounded to 3 digits after the decimal point. The program has to output -1 if Mothy cannot reach his mother.

Sample input and output

Задача 7. «Стена»

Входной файл: wall.in

Выходной файл: wall.out

Ограничение времени: 1 секунда

Поиск по сайту: