IPBLS - Intersection Points Between Line Segments

no tags 

Given N line segments. You should compute the intersection points between those segments using bentley-ottmann algorithm. 

Input

The first line of the input will contain the N.

Then each of the N following lines will contain the points of one of the line segments in the following format:

"x1 y1 x2 y2" where x1 and y1 are the coordinates of the start point of the line segment,

while x2 and y2 are the coordinates of the end point of the line segment. All the coordinates will be integers.

Output

The first line of the output should be the number of points computed lets say M.

Then each of the following M lines should contain one of the intersection points in the following format: "x y"

The points should be ordered by the x coordinate then the y coordinate.

The x and y should be rounded to 2 decimal places.

Example

Input:
2
1 2 4 2
2 0 2 4

Output:
1
2.00 2.00

hide comments
Min_25: 2016-10-02 18:22:08

Please enable all languages.

[Rampage] Blue.Mary: 2016-09-29 15:11:17

You should mention the scoring system in the problem description, or move this problem to classical/tutorial section.

Edit: The range of N and X,Y coordinates should be clearly mentioned in problem description.

Last edit: 2016-09-30 06:48:26

Added by:Omar ElAzazy
Date:2016-09-29
Time limit:1s-2s
Source limit:100000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU