1617 - GluLookAt and hidden point elimination:: HUST Online Judge

1617 - GluLookAt and hidden point elimination

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 10

Solved: 4

Description

In OpenGL world, there is an amazing function called gluLookAt (centre, direction, up). This function can move the camera seamlessly. Imagine the fun time you have in Counter Strike, it’s this function that makes all the amazing 3D effects can be viewed from any perspective. Now it’s your turn to design this function.

Though gluLookAt is amazing, it is also very simple. The basic idea is converting the current coordinate system to camera’s. Formally speaking:

The original coordinate system is formed by 3 perpendicular vectors which are (1, 0, 0), (0, 1, 0), (0, 0, 1), and an origin (0, 0, 0). Similarly, the new coordinate system also formed by 3 perpendicular vectors which are v1, v2, v3 and a given origin o. If a point’s original coordinate is (a,b,c), which can be written as a*(1,0,0)+b*(0,1,0)+c*(0,0,1), then the converted coordinate is (na, nb, nc) which satisfy (a,b,c) = na*v1 + nb*v2 + nc*v3.

What you have to do is to convert a polyhedron in original coordinate system to the new coordinate system, and calculate new coordinate of each vertex of the polyhedron.

Because conversion is too easy, so after conversion, we need you eliminate hidden point. Hidden point elimination means eliminate any point that the line between this point and the camera’s position isintersecting or touching the polyhedron before reach this point. Simply put, hidden point is the point you can’t see from camera.

So you need output all vertex (to be simple, we only consider vertex) of the polyhedron that is invisible (hidden) from the camera.

Input

There are multiple cases, and the first line of input is an integer T denotes the number of cases. In each case, the first four lines are new origin, new X axis, new Y axis, and new Z axis respectively. Next line is an integer N which denotes the number of vertex of polyhedron, then followed by N lines each represent a vertex of the polyhedron. All vertexes are given by 3 integers which are their x coordinate, y coordinate and z coordinate respectively, and these vertexes are given in casual order. The original coordinate system is O(0,0,0), X(1,0,0), Y(0,1,0), Z(0,0,1), and camera is surely outside the polyhedron.

(4 <= N <= 50, all coordinates are smaller than 10^9)

Output

First line is an integer M denotes the number of hidden vertex, and then followed by M hidden vertex with converted coordinate, each vertex occupy one line. Each coordinate keep 3 digits after decimal point.

(For consistency, you should output vertexes which sorted first by x coordinate then by y coordinate and finally by z coordinate, all in increase order)

sample input

sample output

4
-5.000 7.500 2.500
-3.333 7.500 4.167
-1.667 12.500 0.833
0.000 12.500 2.500

hint

source

The 7th(2012) ACM Programming Contest of HUST Problem Setter: Jian He