[ACM 題目] 人格分裂

contents

1. 1. Problem
2. 2. Input
3. 3. Output
4. 4. Sample Input
5. 5. Sample Output
6. 6. More
7. 7. Solution

Problem

某 M 現在正在平面座標上的原點 (0, 0)，現在四周被擺放了很多很多鏡子，某 M 可以藉由鏡子與他的人格小夥伴對話，請問那些鏡子可以見到小夥伴。

鏡子可以當作一個線段，之間不會交任何一點，只要能見到該鏡子中一小段區域就算可見到。

備註：不考慮反射看到。

Input

輸入有多組測資。

每組測資第一行將會有一個整數 n (n < 32767)，表示總共有多少個鏡子。
接著會有 n 行，每一行上會有 4 個整數 sx, sy, ex, ey，表示鏡子所在的線段。

(-32767 < sx, sy, ex, ey < 32767)

Output

對於每組測資輸出一行，每一行將會有 n 個整數 (0/1)，分別表示輸入中第 i 個鏡子是否可見到。

Sample Input

1
5 -5 5 5

4
4 2 5 -2
2 4 6 1
5 5 8 1
3 -4 7 -1

7
-1 2 3 1
2 4 5 -1
-3 -1 1 -2
-1 -4 3 -2
-2 -4 1 -5
-4 1 -1 4
-3 4 -4 3

1
1 1 2 2

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

Sample Output

1
1 1 0 1
1 1 1 1 0 1 0
0
1 0

More

Solution