问题 26645 --D. 降水问题

26645: D. 降水问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 74  解决: 11
[提交][状态][讨论版][命题人:]

题目描述

在一个竖直的平面中,钉着若干条木块,木块不会相交或相接。有一滴水往下落,如果水从s处的落下,那么它将会落到哪一点上?如下图,如果水从Sb开始下降,那么,他将落到Gb点,如果它从Sa处落下,他将落到Ga点。


现在,给定若干木板以及若干水滴的描述,对每一个水滴,求出它会落到X轴上的哪一点。

约定,如下面的图,雨水的路线如下线条所示:



并且,不会有一块水平或者竖直的木板。


输入

第一行有一个正整数n(1≤n≤100),表示木板的条数。以下n行,每一行有4个正整数x1,y1,x2,y2,表示一条连接(x1,y1)与(x2,y2)的木板(1≤x1,y1,x2,y2≤1000)。下面的一行有一个正整数m,表示雨滴的数目(1≤m≤20)。以下m行,每一行有两个正整数,表示雨滴的横坐标与纵坐标(都小于等于1000)。

输出

m行,每一行一个正整数,表示对应的雨滴落地时的横坐标。

样例输入

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

样例输出

10
16
2

来源

 

[提交][状态]