b325. 人格分裂 - 高中生程式解題系統

內容

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

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

備註：不考慮反射看到，保證鏡子不會通過原點。

輸入說明

輸入有多組測資。

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

$1 \le n \le 32767$
$-32767 \le sx, sy, ex, ey \le 32767$

輸出說明

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

範例輸入 #1

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

範例輸出 #1

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

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (50%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <1M
公開測資點#3 (10%): 2.0s , <10M
公開測資點#4 (10%): 2.0s , <10M
公開測資點#5 (5%): 2.0s , <1M
公開測資點#6 (5%): 2.0s , <1M

提示：

上圖為範例測資第二組

上圖為範例測資第三組

請注意極角排序的精準度。

標籤:

計算幾何

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」