ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Timus Top Coders: First Challenge

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Rectangles

Time limit: 1.0 second
Memory limit: 64 MB

Background

It was a warm autumn day, a carpet of fallen leaves rustled underfoot, a light breeze caressingly aired his face, and the sun itself seemed to stretch its rays to the earth...
Hereditary abstract painter Aristarh M. Petroff opened his eyes and swore: "Dammit, what a dream!" Nightmares harassed Mr. Petroff all month long when he painted a series of pictures named "Quadrangles". The series was ordered by some eccentric millionaire, and after the job was completed Aristarh was going to fairly enrich himself. At the thought of money Mr. Petroff grinned. And at that very moment the phone rang:
"Hallo... Yes, Petroff... Glad to hear you, nice weath... what changes?... Well, rather minor... What? Rectangles??! But we have already agre... doesn't matter? An what should I do with already painted... You don't care?... Yes, sure... of course... no problem... all the best."
The millionaire must be really eccentric to change his order at the last moment. Now he wants to buy pictures with rectangles instead of quadrangles. It goes without saying that new pictures should be painted on a level with the highest ideological and artistic standards.
Of course, Aristarh is not going to junk already painted pictures. He just cannot destroy the products of his own creative work, and, after all, new canvases will cost a lot of money. But even now an inspiration has not abandoned Mr. Petroff, and a brilliant idea has come to his mind.

Problem

While creating each of N pictures, Aristarh drew four basic points with cartesian coordinates (x1[i], y1[i]), (x2[i], y2[i]), (x3[i], y3[i]) and (x4[i], y4[i]) on its canvas. Then he connected each pair of the basic points by segments and covered the resulting figure with paint. However the painter is not good in geometry, so sometimes he created triangles or even segments instead of quadrangles. More over, two or more basic points might coincide with each other.
Now Mr. Petroff is going to draw a rectangle on each picture so that each of four already drawn basic points should lie on some side of this rectangle (several points may lie on the same side). No two vertices of the rectangle should coincide with each other (i.e. a point or a segment is not a rectangle). At the same time it should be remembered that each picture is a square 20000*20000 with a center at point (0, 0), and the rectangle should fit this square. A true painter only can think out such thing. And a true programmer only can realize it!

Input

The first line contains the integer number N (0 ≤ N ≤ 10000). Each of the next N lines contains the integer numbers x1[i], y1[i], x2[i], y2[i], x3[i], y3[i], x4[i] and y4[i] (-5000 ≤ x1[i], y1[i], x2[i], y2[i], x3[i], y3[i], x4[i], y4[i] ≤ 5000) for the corresponding picture.

Output

Each of N lines should contain a character "+" (plus) followed by coordinates of the vertices of the desired rectangle for the corresponding picture. The vertices should be listed in clockwise or counterclockwise order. The coordinates should be separated by single spaces and printed with at least six digits after decimal point. If the problem has no solution for some picture, the corresponding line should contain a character "-" (minus). If the problem has several solutions for some picture, the corresponding line should contain any of them.

Sample

input
2
1 0 0 1 3 2 1 2
0 1 0 -1 1 0 -1 0
output
+ 0.000000 0.000000 0.000000 2.000000 3.1234567890 2.000000 3.1234567890 0.000000 
+ 0.000000 -1.000000 1.000000 0.000000 0.000000 1.000000 -1.000000 0.000000
Problem Author: Nikita Rybak, Dmitry Kovalioff, Ilya Grebnov
Problem Source: Timus Top Coders: First Challenge
To submit the solution for this problem go to the Problem set: 1426. Rectangles