На равнинной местности расположен форт, состоящий из трех башен и прямых стен, соединяющих эти башни. Каждую ночь графу Сильвестру, командиру гарнизона, приходится расставлять N стражей. Стражи могут занимать посты внутри форта, на стенах форта или на башнях.
Сильвестр считает расстановку стражей правильной, если их посты расположены выпукло относительно друг друга: для каждого стража точка, в которой расположен его пост, не может принадлежать выпуклой оболочке точек, в которых расположены посты остальных стражей. Другими словами, выпуклая оболочка точек, в которых расположены посты стражей, должна являться выпуклым N-угольником.
Чтобы не портить каждый свой вечер тактическими размышлениями, граф Сильвестр поручает стражам случайно выбрать себе пост в любой точке форта, равномерно и независимо друг от друга.
Какова вероятность того, что при таком случайном выборе постов для N стражей, полученная расстановка будет правильной?
В первых трех строках даны координаты башен: координаты каждой башни задаются парой целых чисел x, y, - 2000 ≤ x, y ≤ 2000. Гарантируется, что координаты башен попарно различны. В четвертой строке дано количество стражей N, 1 ≤ N ≤ 10.
В единственной строке выведите вероятность правильной расстановки стражей с абсолютной погрешностью не более 10 - 4.
-15 -15
15 -15
0 15
3
1.0000000000
-15 -15
15 -15
0 15
4
0.6666666667
