Problem Statement
You want to buy a table with its top being a convex polygon. The vertices of this polygon are described in clockwise order in int[]s x and y. The coordinate of vertex i is (x[i], y[i]).
Unfortunately, the company, which produces tables, is known for very bad quality. Therefore each corner of the table-top may equiprobably have or don't have a table-leg. Table is called stable if there are at least 3 table corners with legs and if table-top's centre of gravity is located strictly inside of the convex hull of all table corners with legs. Return the probability of the table being stable.
Definition
- Class:
- BrokenTable
- Method:
- probStable
- Parameters:
- int[], int[]
- Returns:
- double
- Method signature:
- double probStable(int[] x, int[] y)
- (be sure your method is public)
Notes
- You may assume that the table-top has a constant density and the events "corner i has a leg" are totally independent.
- A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
Constraints
- x will contain between 3 and 50 elements, inclusive.
- y will contain the same number of elements as x.
- Each element of x and y will be between -100 and 100, inclusive.
- The points (x[i], y[i]) will be the vertices of a convex polygon, given in clockwise order.
- No three consecutive table corners will lie on the same straight line.
- The distance between table-top's centre of gravity and any straight line, which passes through some points (x[i], y[i]) and (x[j], y[j]), will be at least 1.0E-6.
Examples
{5, 0, -3}{8, -10, -2}Returns: 0.125
{-8, 6, 8, 6}{8, 1, -3, -4}Returns: 0.1875
The table will be stable in 3 out of 16 possible cases: All legs are present. Corner 2 doesn't have a leg. Corner 3 doesn't have a leg.{0, 0, -3, -8, -6}{10, 9, 4, 6, 8}Returns: 0.28125
{-8, -9, -9, 2, 5, 6, 1, -6}{1, 7, 10, 10, 9, -2, -10, -8}Returns: 0.62109375
Back to all problems