<ПРЕД Задача:
СЛЕД>
Задачу решили 32 пользователя: Jacob, MasterZerg, Ravent, mikleb, DD, tomek, dan, swistak, marek.cygan, maciejk, Rizvanov, crazyb0y, tourist, WsemirZ, JohnJones_001, Chmeli_BSU, DAV, zloy_mipt, mazahaka, RAVEman, defrager, Bogolubsky, fetetriste, TTLovePP, Yagi_Arthur, Dest, ripatti, Kuznetsov_S, Progger, LiuChenheng, regmar, NIGHTFIT.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Разбиение плоскости отрезками

Time limit = 2 секунд(ы)

Найдите число частей, на которую разбили плоскоть данные отрезки.

Вход В первой строке записано число отрезков N, натуральное число, не превосходящее 1000. Затем идут N строк с описание отрезков — декартовы координаты концов отрезков, а именно, целые числа Х1, Y1, Х2, Y2, не превосходящие по модулю 100000.

Выход Количество частей, на которые эти отрезки разбили плоскость (включая "внешнюю" часть).

Оригинальное условие:

На карте, которую Благозвон предложил экспедиции, не было нанесено земли, мелей, тропиков, полюсов и экватора. На ней был только океан и своеобразная "случайная координатная сетка". Случайная координатная сетка представляет собой N отрезков. Концы отрезков могут совпадать. Никакие два отрезка не пересекаются по отрезку. Благозвон сказал, что внутри каждой из частей, на которую отрезки сетки разбивают карту, находится по острову. Выясните, сколько островов представлено на заданной карте.

Вход#1
1 
1 1 2 2
Выход#1
1

Вход#2
4 
0 0 0 1 
0 1 1 1 
1 1 1 0 
1 0 0 0

Выход#2
2

Автор:
Первый индивидуальный Московский контест по программированию, 17 октября 2004, МФТИ. Автор художественного текста -- Олег Христенко.

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 3.214.224.224