How to find your dream room?

Architects of GraphiCity have a strong passion for modelling buildings and they love using building information modelling (BIM) software such as ARCHICAD developed by GRAPHISOFT.

However, these architects usually dive into the details and are not aware of some essential information, such as the best located room or the number of rooms in the planned building. Your task is to help the architects to answer these questions.

To keep it simple, now we are focusing on the two-dimensional floor plan layout of the building, where there are only walls. These walls intersect in only their ending points and they are represented by single lines, sectors. All the ending coordinates of the walls are integer. Both ending points of a wall is connected to at least one other wall.

The rooms — by definition — are the closed regions bounded by these walls which don’t contain any other walls.

We assume that the origin point is inside a room and it does not lie on any of the walls.

We have two sub-tasks:

  1. For a given layout, find the room containing the origin point (0, 0).
  2. For a given layout, determine the number of rooms in the building.

We also have two levels of difficulty.

  • A. All walls are parallel to the axes.
  • B. Walls could be non-parallel to the axes.

So you have four different tasks to implement: A1, A2, B1, B2.

Input:

The first line of the input file contains a single integer N denoting the number of walls. (1 <= N <= 1000.)

Each of the next N lines contains four integers A, B, C, D where (A, B) and (C, D) are the coordinates of the ending points of the wall. The coordinates are between -1000 and 1000.

Output for A1 and B1:

Print a single integer K to the first line, where K is the number of the walls on the boundary of the room containing the origin point (0, 0).

Each of the next K line should contain two integers X, Y where (X, Y) is a corner point of the room-boundary walls. These points should be in a consecutive way.

Output for A2 and B2:

Print a single line with a single integer: the number of the rooms.

Sample input:

31
-6 -2 -6 -4
-5 4 -5 -2
-4 -2 -4 -4
-3 2 -3 1
-3 1 -3 -2
-2 1 -2 -1
-1 4 -1 2
-1 -3 -1 -4
1 -3 1 -5
2 2 2 -1
2 -1 2 -3
3 4 3 -1
4 -2 4 -5
5 -1 5 -2
-5 4 -1 4
-1 4 3 4
-3 2 -1 2
-1 2 2 2
-3 1 -2 1
-2 -1 2 -1
2 -1 3 -1
3 -1 5 -1
-6 -2 -5 -2
-5 -2 -4 -2
-4 -2 -3 -2
4 -2 5 -2
-1 -3 1 -3
1 -3 2 -3
-6 -4 -4 -4
-4 -4 -1 -4
1 -5 4 -5

Sample output for A1 and B1:

7
2 -1
2 2
-1 2
-3 2
-3 1
-2 1
-2 -1

Sample output for A2 and B2:

6

Input files:

algorithm

Criteria

  • Idea of solution for a subtask
  • (1 point × 4 subtasks)
  • Appropriate algorithm for a subtask (1 point × 4 subtasks)
    • Right answer for the test cases
  • Code quality
  • (1 point)
  • Speed
  • (1 point)

Submission

To present your solution for any of these four subtasks, find the mentors of Graphisoft.
The difficulty of these subtasks widely varies, so if you have some ideas or even a basic solution, don’t hesitate to consult the mentors.