Problem G. Birthday Cake

Background

Lucy and Lily are twins. Today is their birthday. Mother buys a birthday cake for them.Now we put the cake onto a Descartes coordinate. Its center is at (0,0), and the cake's length of radius is 100.

There are 2N (N is a integer, 1<=N<=50) cherries on the cake. Mother wants to cut the cake into two halves with a knife (of course a beeline). The twins would like to be treated fairly, that means, the shape of the two halves must be the same (that means the beeline must go through the center of the cake) , and each half must have N cherrie(s). Can you help her?

Note: the coordinate of a cherry (x , y) are two integers. You must give the line as form two integers A,B(stands for Ax+By=0), each number in the range [-500,500]. Cherries are not allowed lying on the beeline. For each dataset there is at least one solution.

Input

Output

Sample Input

2
-20 20
-30 20
-10 -50
10 -5
0

Sample Output

0 1

#include <stdio.h>
int x[100], y[100];
int test(int A, int B, int N) {
    static int i, pos, neg, tmp;
    pos = 0, neg = 0;
    for(i = 2*N-1; i >= 0; i--) {
        tmp = A*x[i] + B*y[i];
        if(tmp < 0)
            neg ++;
        else if(tmp > 0)
            pos ++;
        else
            return 0;
    }
    return pos == neg;
}
void find(int N) {
    int A, B;
    while(1) {
        A = rand()%1001-500;
        B = rand()%1001-500;
        if(test(A, B, N)) {
            printf("%d %d\n", A, B);
            break;
        }
    }
}
int main() {
    int N, i;
    while(scanf("%d", &N) == 1 && N) {
        for(i = 2*N-1; i >= 0; i--)
            scanf("%d %d", &x[i], &y[i]);
        find(N);
    }
    return 0;
}