2011年10月22日 星期六

833 - Water Falls


考慮下圖中的三個線段P1, P2, P3,請將它們視為平面,假設雨水Sa從天空中垂直落下,碰到P3與P1後會沿著平面流動,最終落在地平面Ga處,同理,由Sb處掉落的雨水最終會落在Gb處。

\epsfbox{p833a.eps}
給定多條線段與多個點,本題請你計算落點在何處,為了簡化本問題,你可以假設不會有水平線段或是交叉的線段,且所有點(包含線段的端點)的垂直投影皆不相同。

Input

輸入的一開始會給定一個正整數,表示接下來有幾組測試資料,每組測試資料前面皆會有一空白列。
每組測試資料的一開始會給定整數NP,表示接下來有NP條線段,每條線段以兩個端點座標表示,分別為x1 y1 x2 y2(以一個空白字元隔開)。接下來會有一個整數NS表示有幾組雨水的初始位置,接下來NS列,每列有一整數對x y(以一個空白字元隔開)表示雨水的位置。

Output

請在每組測試資料中間輸出一列空白。
每組測試資料請輸出NS列分別表示落點的 x 座標。

Sample Input 

1

4
14 7 3 4
11 13 16 11
1 10 6 7
2 1 4 3
3
10 4
14 14
2 13

Sample Output 

10
16
2
上例的圖形繪出如下:

\epsfbox{p833b.eps}


原文出處

沒有留言:

張貼留言