Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shadow Business

Limits: 1s, 128 MB

The result of the S.S.C exam is published. And Poltu has got A+. Poltu is very happy for his achievement and so he asked his elder brother Boltu to give him a treat. But Boltu doesn’t care about A+ and so he has told Poltu that he will give Poltu a treat if and only if Poltu can solve a mathematical problem. Since Boltu likes teamwork, so he allows Poltu to take help from one of his friends. As you are Poltu’s best friend, can you help Poltu to solve this math?

In this problem, you are given a 3D convex polyhedron and a point light source on 3-dimensional space. It is guaranteed that there will be a shadow on the XY plane. Calculate the area of the shadow.

Input

1st Line of the input will contain an integer N (3 < N < 61). Each of the following N lines will contain 3 integers x, y, z (2 ≤ x, y, z ≤ 200) representing the vertices of a convex polyhedron. Next, there will be 3 integers lx, ly, lz (0 ≤ lx, ly ≤ 300 and 300 ≤ lz ≤ 400), which is the co-ordinate of the point light source.

Output

For each case print the area of the shadow cast by the convex polyhedron on XY plane. Errors less than 10-4 will be ignored.

Samples

InputOutput
8
2 2 2
2 2 6
2 6 2
2 6 6
6 2 2 
6 2 6
6 6 2
6 6 6
4 4 8
256.000000000
6
2 4 4
6 4 4 
4 2 4
4 6 4
4 4 2
4 4 6
4 4 8
32.000000000

The Constraint for lz is violated in the samples for a better understanding of the problem.

Definitions:

Convex Polyhedron: A convex polyhedron is a bounded structure with a finite number of vertices connected by polygonal faces along with the condition that if you connect any two points in the structure by a line, that line will be contained within the bounded structure.

Point light source: In mathematical modeling, we often consider point sources to simplify our initial models. Here, we have the same thing. Light is emitted in all directions (4*pi steradians) from a point.

(If you can solve this problem during the contest, you will surely get a Treat ;-))

Authors
  • jackal_1586's Avatar

    jackal_1586

  • draak_krijger's Avatar

    draak_krijger

Discussion
Submit

Login to submit