F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

geometric problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 86    Accepted Submission(s): 20
Special Judge


Problem Description
There are six points $ABMNXY$ in a two-dimensional plane.

As shown in the figure below, $ABNM$ and $XYNM$ are both in convex quadrilateral shapes, and their intersection area is $0$. You are also given two lines $L1$ and $L2$. You have to choose one point on each line (for example, $S$ on $L1$ and $T$ on $L2$) so that the area of $ABS$, $MSNT$, and $XYT$ are at the same size. Moreover, $S$ should lie within or be on the border of $ABNM$, and $T$ should lie within or be on the border of $XYNM$. Please output the positions of $S$ and $T$ that you choose!

 

Input
The first line contains an integer $T$ indicating the number of test cases.

Each test case consists of three lines. The first line contains $12$ integers, $A_x, A_y, B_x, B_y, M_x, M_y, N_x, N_y, X_x, X_y, Y_x, Y_y$, denoting the $x$ and $y$ coordinates of points $A,B,M,N,X,Y$. The second line contains $4$ integers, $L1_{1,x}, L1_{1,y}, L1_{2,x}$, and $L1_{2,y}$, denoting two distinct points on $L1$. The third line also contains $4$ integers, $L2_{1,x}, L2_{1,y}, L2_{2,x}$, and $L2_{2,y}$, denoting two distinct points on $L2$.

* $1 \le T \le 20$

* coordinates are in the range $[0, 514]$

* $L1_1 \neq L1_2$, $L2_1 \neq L2_2$
 

Output
For each test case output $4$ numbers in a single line, $S_x, S_y, T_x, T_y$, denoting the two chosen points. If there are multiple solutions, output the one with the smallest $S_x$. If there are still multiple solutions, output the one with the smallest $S_y$, and then the smallest $T_x$, and then the smallest $T_y$. Otherwise, if there are no solution, output "-1" (without quotes) in one line. A solution with an absolute error at most $10^{-6}$ will be accepted.  
 

Sample Input
1 0 10 0 0 5 10 5 0 10 10 10 0 0 0 5 10 5 0 10 10
 

Sample Output
3.333333333333 6.666666666667 6.666666666667 3.333333333333
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 23:21:40, Gzip enabled