0157. Areas

Имя входного файла:	areas.in
Имя выходного файла:	areas.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Consider N different lines on the plane. They divide it to several parts, some of which are finite, some infinite.

Your task in this problem is for each finite part to find its area.

Input file

The first line of the input file contains N – the number of lines ({1 ≤ N ≤ 80}). Each of next N lines contains four integer numbers x₁, y₁, x₂ and y₂ – the coordinates of two different points of the line.

All coordinates do not exceed 10² by their absolute value.

No two lines coincide.

Output file

First output K – the number of finite parts among those the lines divide the plane to.

Next K lines of the output file must contain area parts sorted in non-decreasing order. You answer must be accurate up to 10^-4.

Due to floating point precision losses possible, do not consider parts with area not exceeding 10^-8.

Examples:

areas.in	areas.out
5 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1	2 0.5000 0.5000

Источник: Petrozavodsk Summer 2003. Final Contest, Saturday, August 30
Автор: Andrew Stankevich

Обсудить       Отправить решение



Версия для печати