Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
POOL2016

H. Нарешті фізика!

Задача POOL2016 У Жмеринці побудували фонтан. Звичайно, з вінницьким він не зрівняється, проте в нього є цікава особливість. Фонтан побудований таким чином - проведено величезну кількість горизонтальних труб, відстань між двома сусідніми дорівнює одному метру. Аналогічно, перпендикулярно до них проведені і вертикальні труби. Горизонтальні і вертикальні труби перетинаються у деяких точках. Саме в цих точках напір води дуже великий і створюється фонтан. Бізнесмен Петро вирішив обмежити фонтан і зробити з нього басейн(у Жмеринці немає гарних шкіл тому й бізнесмени не занадто розумні). Петро обрав N точок і побудував опуклий многокутник, що і є основою майбутнього басейну. Так вийшло, що частина фонтанів залишилась усередині многокутника, Петро буде використовувати їх для набору води. Але, щоб вода в басейні була чистою, у точках перетину труб, що належать сторонах басейну і не є кутами басейну, було прийнято рішення зробити злив води. Таким чином, басейн буде мати M фонтанів у середині та T зливів на краях. Важливо відмітити, що швидкість потоку води у фонтані //codeforces.com/predownloaded/01/c1/01c1b0aaf8f7fd75c9829e96cf09ec92d6e48d44.png, а швидкість зливу //codeforces.com/predownloaded/cc/87/cc872b6497d24e067012a93a5e689c8df03f6691.png. Знайдіть, через скільки секунд глибина басейну буде хоча б К, якщо стінки басейну перпендикулярні до його основи.

Вхідні дані

У першому рядку вхідних даних записано чотири числа - N(1 ≤ N ≤ 103) - кількість сторін у многокутнику, M - кількість фонтанів у многокутнику, T - кількість зливів , К(0 ≤ K ≤ 106) - необхідна глибина басейну. Далі у N стрічках знаходяться N пар цілих чисел, координати басейна у порядку обходу за або проти годинникової стрілки. Координати не перевищують 106 за абсолютним значенням.

Вихідні дані

Виведіть одне дійсне число з максимальною точністю - через скільки секунд рівень води у басейні буде хоча б К метрів. Якщо такого ніколи не відбудеться, то виведіть - 1.

Приклади

 

Вхідні дані

4 9 0 3
0 1
1 4
4 5
2 0

Вихідні дані

3.3333333333

 

Вхідні дані

4 15 16 2
0 0
0 4
6 4
6 0

Вихідні дані

-1

Коментар

Коментар для тих, хто знає фізику. Тиск води не впливає на швидкість потоку води у фонтані. Вода набирається рівномірно, під час набору води зливи працюють.


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"