Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

TETRAHE1 - Point in tetrahedron

There're given 5 points in 3D coordinates (integers 0<=x,y,z<100). Their order is arbitrary. 4 of them are the vertices of a tetrahedron whose edges can be of different size. One is lying in this tetrahedron. Find its index (1-5) in the array of points.

Input

In the first line the number T (T<100) of test cases.
Then for each test case 5 lines with the space separated x-, y- and z-coordinates of the 5 points.

Output

For each test case a line with the index of that point which is lying in the tetrahedron formed of the 4 other points.

Example

Input:
1
5 72 66
92 23 68
60 60 49
74 78 33
67 76 27 Output: 3

Added by:HWK
Date:2011-08-07
Time limit:0.740s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: SCM qobi

hide comments
2011-09-22 17:51:48 Jander
Yeah, I figure that some of this code can be reused for EQUASOLV.
2011-09-22 17:35:31 HWK
@Jander: Then that's the right time to solve EQUASOLV. ;-)
2011-09-22 15:45:17 Jander
This has turned out to be a harder one than I originally thought. It's certainly pushed my data manipulation techniques to new limits :-) And in the process I managed to trounce the Ruby version too ;-)
2011-09-22 14:35:45 HWK
@Jander: Great job!
Sorry, I saw your comment too late. I'd surely have given you an error example. But you solved it on your own. Much better. :-)
2011-09-17 14:17:55 Jander
HWK: You couldn't give me an example of vertices that my submissions are failing on ? I'm sure my logic is correct, so can't visualise a set that it would fail on. Thanks.

Edit: Ah, I've just seen your replies on the main SPOJ version, and mine fails on one of those sets of vertices. Most odd. Now to fix it.

Edit #2: Interesting set of points :-) Back to the drawing board I think.

Last edit: 2011-09-17 15:35:02
2011-08-21 11:13:38 HWK
@hallvabo: I take my hat off to you. :-)
2011-08-21 11:09:59 Hallvard Norheim Bø
@hwk: Yes, but I was too tired to continue. 26 seconds after your improvement, I got it down to 206 bytes :)
2011-08-21 11:05:29 HWK
@hallvabo: Done, but only 3 Ruby bytes saved.
Your 228 solution is very impressive but as you see it can be improved more.

Last edit: 2011-08-21 11:14:36
2011-08-21 00:52:54 Hallvard Norheim Bø
Python is doing fine :)
I still got some tricks to try, so maybe you should think about improving the Ruby solution...
2011-08-20 17:36:51 HWK
@hallvabo: I haven't checked it. But most of the test data are random. Thus you have to reckon with angles above 90°.
btw: Very nice Python solution. Sorry, that your favorite language works so bad at this task. Perhaps you should try Ruby.

Last edit: 2011-08-20 17:40:27
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.