3430. Urban Design

单点时限: 4.0 sec

内存限制: 512 MB

A new town is being planned, and the designers have some very specific ideas about how things should be laid out. First, they lay out the streets. Each street is perfectly straight and passes completely from one end of the town to the other. These streets divide the town into regions, and each region is to be designated either residential or commercial. The town planners require that any two regions directly across the street from one another must have different designations. On this one particular day, all of the streets have been planned, but none of the regions have been designated. One town planner wishes to purchase two properties, and it is important to him that the properties eventually have different designations. For this problem, the streets can be modeled by lines in the plane that extend forever in both directions and have no width, and properties may be modeled by points. Given the lines and two points, can you decide whether or not
they must get different designations, commercial or residential?


Input begins with an integer $S$ on a single line, giving the number of streets ($1 \le S \le 10\,000$).

The next $S$ lines of input each contain four integers $x_1$, $y_1$, $x_2$, and $y_2$, specifying the coordinates of two distinct points $(x_1, y_1)$ and $(x_2, y_2)$. The unique line through these two points gives one of the streets. Each
coordinate is in the range $[0, 10\,000]$, and no two lines will be identical. That is, the town will have $S$ distinct streets.

The next line contains an integer $T$, the number of pairs of properties to test ($ 1 \le T \le 1\,000$).

This is followed by $T$ lines of input, each containing four integers $x_3$, $y_3$, $x_4$, and $y_4$, representing two distinct points $(x_3, y_3)$ and $(x_4, y_4)$, where each point lies within one of the two properties to test. None of
these points will lie on any of the streets, nor will both points lie within the same property. Again, each coordinate is in the range $[0, 10\,000]$.


For each of the $T$ pairs of properties to be tested, output either same if the properties are guaranteed to receive the same designation or different if they are guaranteed to receive different designations.


1 1 2 1
1 1 1 2
2 0 2 2
2 0 0 3
0 0 2 2
1 3 2 4
1 3 2 5
1 3 3 4
7 9 8 8
14 7 10 13
1 4 2 3

5 人解决,7 人已尝试。

5 份提交通过,共有 28 份提交。

7.5 EMB 奖励。

创建: 6 年,7 月前.

修改: 6 年,7 月前.

最后提交: 2 月,2 周前.

来源: NCNA 2017