#D4579. Hole
Hole
Hole
Problem Statement
Mr. Hagiwara, a witch, has a very negative personality. When she feels depressed, she uses the magic of digging to make holes and cry and fill them. The magic of digging is as follows.
She first draws N line segments on the ground. And when she casts the spell, a hole is created in the area surrounded by the line. Two holes that are in a crossing / inclusion relationship are counted as one hole. However, two holes that are in contact only at the vertices are counted as separate holes.
Figures 1 and 2 show Sample Inputs 1 and 2. First, in FIG. 1, since the triangle A and the triangle B are in contact with each other only at the vertices, they are counted as separate holes. Since the B triangle and the C triangle overlap each other, they are counted as one hole. Therefore, FIG. 1 shows two holes. In Figure 2, the D rectangle is contained within the E rectangle, so these are counted as one hole. Since E also intersects the hole in the upper right, Fig. 2 shows one hole.
You are the caretaker of Mr. Hagiwara and you have to fill the myriad holes she made. Create a program to find out how many holes she made to find out how many holes she had to fill.
Constraints
- 1 <= N <= 50
- -1000 <= coordinates <= 1000
- The positions of (xai, yai) and (xbi, ybi) are different
- When two line segments intersect, the four endpoints of the two line segments will not line up in a straight line.
Input
Each data set is input in the following format.
N xa1 ya1 xb1 yb1 xa2 ya2 xb2 yb2 ... xaN yaN xbN ybN
All inputs are represented by integers. The first line is the number of line segments. Then, line segment information is given over N lines. One line segment is represented by the endpoints (xai, yai) and (xbi, ybi) of the line segment.
Output
Output the number of holes in one line.
Examples
Input
8 5 0 5 10 5 10 0 5 0 5 5 0 10 0 10 10 10 10 5 5 5 5 10 0 10 2 15 5 15 5 10 8
Output
2
Input
11 0 0 10 0 10 0 10 10 10 10 0 10 0 10 0 0 1 2 9 2 8 1 8 9 9 8 1 8 2 9 2 1 8 11 11 8 8 11 14 10 11 8 10 14
Output
1
inputFormat
Inputs 1 and 2. First, in FIG. 1, since the triangle A and the triangle B are in contact with each other only at the vertices, they are counted as separate holes. Since the B triangle and the C triangle overlap each other, they are counted as one hole. Therefore, FIG. 1 shows two holes. In Figure 2, the D rectangle is contained within the E rectangle, so these are counted as one hole. Since E also intersects the hole in the upper right, Fig. 2 shows one hole.
You are the caretaker of Mr. Hagiwara and you have to fill the myriad holes she made. Create a program to find out how many holes she made to find out how many holes she had to fill.
Constraints
- 1 <= N <= 50
- -1000 <= coordinates <= 1000
- The positions of (xai, yai) and (xbi, ybi) are different
- When two line segments intersect, the four endpoints of the two line segments will not line up in a straight line.
Input
Each data set is input in the following format.
N xa1 ya1 xb1 yb1 xa2 ya2 xb2 yb2 ... xaN yaN xbN ybN
All inputs are represented by integers. The first line is the number of line segments. Then, line segment information is given over N lines. One line segment is represented by the endpoints (xai, yai) and (xbi, ybi) of the line segment.
outputFormat
Output
Output the number of holes in one line.
Examples
Input
8 5 0 5 10 5 10 0 5 0 5 5 0 10 0 10 10 10 10 5 5 5 5 10 0 10 2 15 5 15 5 10 8
Output
2
Input
11 0 0 10 0 10 0 10 10 10 10 0 10 0 10 0 0 1 2 9 2 8 1 8 9 9 8 1 8 2 9 2 1 8 11 11 8 8 11 14 10 11 8 10 14
Output
1
样例
11
0 0 10 0
10 0 10 10
10 10 0 10
0 10 0 0
1 2 9 2
8 1 8 9
9 8 1 8
2 9 2 1
8 11 11 8
8 11 14 10
11 8 10 141