ACM 10167 Birthday Cake

這題用到一個基本的數學概念：
假設有一條直線L: ax+by=0，(m, n)的位置在L的右邊
則將(m, n)代入L的值會>0， 即a*m+b*n會>0
反之，若(m, n)在L的左邊，則a*m+b*n<0

知道這個基本的概念以後，程式就不難寫了
不斷窮舉a, b的值，每窮舉出一組(a,b)就把題目給的點代進去
(1)若代入>0，則代表這個點在直線的右邊，紀錄下來
(2)若代入<0，則代表這個點在直線的左邊，紀錄下來
所有點都代入以後，看看左邊的點和右邊的點的數目是否相同，若相同則代表此組(a, b)為一解

Code #1
#include <stdio.h>

int main(void)
{
    int a, b, i, n, c1, c2, tmp, found, pos[100][2];

    while (scanf("%d", &n) == 1 && n)
    {
        n *= 2;
   
        found = 0;
        for (i = 0; i < n; i++)
            scanf("%d%d", &pos[i][0], &pos[i][1]);
        for (a = 500; a >= -500 && !found; a--)
        {
            for (b = 500; b >= -500 && !found; b--)
            {
                if (a == 0 && b == 0)
                    continue;
                c1 = c2 = 0;
                for (i = 0; i < n; i++)
                {
                    tmp = a*pos[i][0]+b*pos[i][1];
                    if (tmp > 0)
                        c1++;
                    else if (tmp < 0)
                        c2++;
                    else
                        break;
                }
                if (c1 == c2 && tmp)
                {
                    printf("%d %d\n", a, b);
                    found = 1;
                }
            }
        }
    }
   
    return 0;
}



如果今天題目要求要輸出所有的解，並且不能重複(也就是3x+6y=0和x+2y=0不能都出現)
那就只要在窮舉出一組(a, b)後就先看看是否互質即可
還有found變數要拿掉，才會窮舉所有解

Code #2
#include <stdio.h>

int gcd(int a, int b)
{
    int tmp;
   
    while (b != 0)
    {
        tmp = b;
        b = a%b;
        a = tmp;
    }
    return a;
}

int main(void)
{
    int a, b, i, n, c1, c2, tmp, pos[100][2];
   
    while (scanf("%d", &n) == 1 && n)
    {
        n *= 2;
        for (i = 0; i < n; i++)
            scanf("%d%d", &pos[i][0], &pos[i][1]);
        for (a = 500; a >= -500; a--)
        {
            for (b = 500; b >= -500; b--)
            {
                if ((a == 0 && b == 0) || gcd(a, b) != 1)
                    continue;
                c1 = c2 = 0;
                for (i = 0; i < n; i++)
                {
                    tmp = a*pos[i][0]+b*pos[i][1];
                    if (tmp > 0)
                        c1++;
                    else if (tmp < 0)
                        c2++;
                    else
                        break;
                }
                if (c1 == c2 && tmp)
                    printf("%d %d\n", a, b);
            }
        }
    }
   
    return 0;
}