Problem : 155 - 線段相交

Problem Statistics

Solved Member: 20　　Submission: 99　　User Tried: 21

Statement:

有 n(n <= 250) 條線，有水平和垂直的兩種。其中兩種平行的線碰在一起不會怎樣。不過兩條垂直的線若交在一點你會覺得很不爽。

給你很多條線以及他們的座標，你希望找出最多的線使他們之間都互相不相交。

Input:Output:

第一行有一個正整數 n，代表有 n 條線。
後面 n 行每行有四個數字 x1,y1,x2,y2，範圍在 1 與 10^9 之間。代表線段的兩端點在(x1,y1)與(x2,y2)，其中現段的長度不為0。
其中每條線必定滿足 x1=x2 或 y1=y2 之一。(水平或者垂直)

請輸出一個數字，代表你最多可以選幾條線。

Sample Input:Sample Output:

3
4 5 10 5
6 2 6 12
8 3 8 5

Source:

USACO 2011 Nov. Gold

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10