Hole

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem G: 穴掘って埋まってます

Problem Statement

魔法使いの萩原さんは、非常にネガティブな性格である。彼女は、何か落ち込むようなことがあると、穴掘りの魔法を使って穴を作り、泣きながら埋まってしまう。穴掘りの魔法とは、次のようなものである。

彼女は、まずN本の線分を地面に描く。そして、彼女が呪文を唱えると、線で囲まれた範囲に穴が出来上がる。交差・内包の関係にある2つの穴は、1つの穴として数える。ただし、頂点のみで接している2つの穴は、別々の穴として数える。

図1と図2に、Sample Input 1と2の図を示す。まず、図1において、Aの三角形とBの三角形は、頂点のみで接しているため、別々の穴と数える。Bの三角形とCの三角形は、辺同士重なっているため、1つの穴として数える。よって、図1は、穴2つである。図2では、Dの四角形がEの四角形に包含されているため、これらは1つの穴と数える。Eは、右上の穴とも交差しているため、図2は、穴1つである。

あなたは、萩原さんの世話係であり、彼女が作った無数の穴を埋めなければならない。どれくらい穴を埋めないといけないのかを知るために、彼女が作った穴の数を求めるプログラムを作成せよ。

Input

各データセットは、以下の形式で入力される。

N
xa1 ya1 xb1 yb1
xa2 ya2 xb2 yb2
...
xaN yaN xbN ybN

入力は全て整数で表わされる。1行目は、線分の数である。続いてN行にわたって、線分の情報が与えられる。1つの線分は、線分の端点(xai, yai)と(xbi, ybi)によって表わされる。

Constraints

  • 1 <= N <= 50
  • -1000 <= 座標 <= 1000
  • (xai, yai)と(xbi, ybi)の位置は異なる
  • 2つの線分が交差しているとき、2つの線分の端点4つが一直線上に並ぶことはない

Output

穴の個数を1行で出力せよ。

Sample Input 1

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 for the Sample Input 1

2

Sample Input 2

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 for the Sample Input 2

1

Source: Ritsumeikan University Programming Contest 2013 , Aizu Commpetitive Programming Camp 2013 Day 1, Japan, 2013-09-03
Problem Setter:  Respect2D