Comet OJ

C0431 [CEOI2002Day2] A highway and the seven dwarfs

内存限制：256 MB 时间限制：5000 ms

题目描述

Once upon a time, there was a land where several families of dwarfs were living. This land was called Dwarfland. Each family lived in one house. Dwarfs were often visiting their friends from the other families. Because the Dwarfland was free of evil, it happened that each dwarf visited each other during some short period of time.

Once, the humans living in countries around Dwarfland decided to build several straight highways. As the humans weren’t aware of the dwarfs, some of the planned highways passed through Dwarfland. The dwarfs discovered this and were quite unhappy about it. The dwarfs are very little, and also very slow, so they are unable to cross the highway safely.

The dwarfs managed to get the plans for the highways somehow, and now they need your help. They would like to keep on visiting each other, so they don’t like those highways which divide their houses into two non-empty parts. After they find out which highways they don’t like, they will magically prevent the humans from building them.

The dwarfs are very little, and cannot reach the keyboard. So they asked for your help.

Task

Given is a number $N$ of points (houses) in the plane and several straight lines (highways). For each given line, your task is to determine whether all $N$ points lie on the same side of the line or not. Your program has to output the answer for the currently processed linebeforereading the description of the next one. You may assume that no highway passes through any of the houses.

输入格式

Your program is supposed to read the input from the standard input (stdin in C/C++) and write its output to the standard output (stdout in C/C++). The first line of the input contains one integer $N (0 ≤ N ≤ 100000)$. $N$ lines follow, the $i-th$ of them contains two real numbers $x_i, y_i (−10^9 ≤ x_i,y_i ≤ 10^9)$ separated by a single space – the coordinates of the $i-th$ house.

Each of the following lines contains four real numbers $X_1, Y_1, X_2, Y_2 (−10^9 ≤ X_1,Y_1,X_2,Y_2 ≤ 10^9)$ separated by a single space. These numbers are the coordinates of two different points $[X_1,Y_1]$ and $[X_2,Y_2]$, lying on the highway.

输出

For each line of input, your program is supposed to output a line containing the string “GOOD” if all of the given points are on the same side of the given line, or “BAD” if the given line divides the points. After writing out each line of the output, your program should flush the output buffer. In the following sections you may find an example on how to do this.

We will terminate your program after it gives the answer for the last highway. Your program is not supposed to terminate by itself. You may assume that there will be no more than $100000$ highways.

样例

样例输入 1

4
0.0 0
6.00 -0.001
3.125 4.747
4.747 0.47
5 3 7 0
4 -4.7 7 4.7
4 47 4 94

样例输出 1

GOOD
BAD
BAD

提示

Input and output routines in C/C++

Reading one line (note that there is no space after the last%lf):

double X_1, Y_1, X_2, Y_2;
scanf(" %lf %lf %lf %lf",&X_1,&Y_1,&X_2,&Y_2);

Writing the output for one line:

printf("GOOD\n"); fflush(stdout);

Warning

You are adviced to use thedoubledata type to store real numbers. Note that when using real number arithmetics, rounding errors may occur. If you want to test, whether two real numbers $x, y$ are equal, don’t test whether $x = y$ but whether $|x−y| < ε$ (where $ε$ is a small constant, $10^{−4}$ will suffice).