402950: GYM100957 E Стража

E. Стражаограничение по времени на тест1 секундаограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

На равнинной местности расположен форт, состоящий из трех башен и прямых стен, соединяющих эти башни. Каждую ночь графу Сильвестру, командиру гарнизона, приходится расставлять 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