Problem C
Urban Design
Input
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]$.
Output
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.
Sample Input 1 | Sample Output 1 |
---|---|
2 1 1 2 1 1 1 1 2 3 2 0 2 2 2 0 0 3 0 0 2 2 |
different same same |
Sample Input 2 | Sample Output 2 |
---|---|
4 1 3 2 4 1 3 2 5 1 3 3 4 7 9 8 8 2 14 7 10 13 1 4 2 3 |
same different |