Submit  All submissions  Best solutions  Back to list 
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 (15) 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 zcoordinates 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:  20110807 
Time limit:  0.740s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: SCM qobi 
hide comments


20110922 17:51:48 Jander
Yeah, I figure that some of this code can be reused for EQUASOLV. 

20110922 17:35:31 HWK
@Jander: Then that's the right time to solve EQUASOLV. ;) 

20110922 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 ;) 

20110922 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. :) 

20110917 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: 20110917 15:35:02 

20110821 11:13:38 HWK
@hallvabo: I take my hat off to you. :) 

20110821 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 :) 

20110821 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: 20110821 11:14:36 

20110821 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... 

20110820 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: 20110820 17:40:27 