СТЕНИ
След много месеци непрекъсната работа в новата си фирма, Пиер решил да си вземе почивка и да посети забележителностите на Далечния изток. Той посетил и забележителната Велика китайска стена, но още по-голямо впечатление му направил комплекс от защитни стени в планините на Тибет. Комплексът се състоял от множество къси, прави стени, някои от които се пресичали една с друга, образувайки сложна система от защитни съоръжения. Там където се пресичали две стени били изградени защитни кули. Пиер изкачил не една от тях и се наслаждавал на прекрасната гледка, която му предоставяла всяка кула. Разхождайки се из огромния комплекс той се замислил, не са ли прекалено много стените и не са ли прекалено близко защитните кули. Така възникнал въпросът, на какво разстояние са двете най-близки кули. За целта Пиер съставил модел на комплекса, като съпоставил на стените отсечки в правоъгълна координатна система, а на кулите – съответните пресечни точки. Комплексът за съжаление бил прекалено голям за да може да се реши задачата на ръка, но като опитен програмист, Пиер видял, че това е лесна работа за един компютър.
Дадени са N (3 ≤ N ≤ 50000) отсечки в равнината. Напишете програма WALLS.EXE, която намира разстоянието между двете най-близки пресечни точки на отсечки. Броят на различните пресечните точки, ще бъде поне две и по-малък от 1000000.
Първият ред на входния текстов файл WALLS.INP, ще съдържа числото N. Следват N реда с по четири цели числа на всеки от тях – X1, Y1, X2, Y2, разделени с по един интервал, задаващи двата края на по една отсечка. Координатите ще бъдат числа по-малки от 1000000000 по абсолютна стойност.
Изходният текстов файл WALLS.OUT, трябва да съдържа едно число – разстоянието между двете най-близки пресечни точки. Числото трябва да бъде дробно десетично, с точност 1е-6.
ПРИМЕР
Вход
5
10 20 10 30
8 23 12 29
80 1 80 30
70 20 90 20
70 15 90 15
Изход
5
Сподели с приятели: |