好气，一个弱智问题导致wa了好几次。


Source Code
Problem: 1034		User: bixiongquan
Memory: 416K		Time: 16MS
Language: GCC		Result: Accepted

    Source Code

    #include <stdio.h>
    #include <math.h>
    #include <string.h>

    #define DOG_SPEED 2

    #define MAX_POINT_NUM 101

    #define TRUE  (int)1
    #define FALSE (int)0

    typedef int BOOL;

    typedef struct
    {
        int x;
        int y;
    }Point;

    typedef struct
    {
        int num;
        Point pos[MAX_POINT_NUM];
    }Points;

    Points g_Bob;
    Points g_interests;
    BOOL g_isOccupied[MAX_POINT_NUM];
    int g_len[MAX_POINT_NUM][MAX_POINT_NUM];
    int g_selectNum;
    int g_selectIdx[MAX_POINT_NUM];
    int g_BobToInterest[MAX_POINT_NUM];

    void Input()
    {
        int i;

        scanf("%d %d", &g_Bob.num, &g_interests.num);

        for(i = 0; i < g_Bob.num; i++)
        {
            scanf("%d %d", &g_Bob.pos[i].x, &g_Bob.pos[i].y);
        }

        for(i = 0; i < g_interests.num; i++)
        {
            scanf("%d %d", &g_interests.pos[i].x, &g_interests.pos[i].y);
        }

        g_selectNum = 0;
        memset(g_len, -1, sizeof(g_len));
        memset(g_selectIdx, -1, sizeof(g_selectIdx));
        memset(g_BobToInterest, -1, sizeof(g_BobToInterest));
    }

    void Output()
    {
        int bobIdx, interestIdx;

        printf("%d\n", g_Bob.num+g_selectNum);

        for(bobIdx = 0; bobIdx < g_Bob.num; bobIdx++)
        {
            printf("%d %d ", g_Bob.pos[bobIdx].x, g_Bob.pos[bobIdx].y);
            interestIdx = g_BobToInterest[bobIdx];
            if(interestIdx != -1) printf("%d %d ", g_interests.pos[interestIdx].x, g_interests.pos[interestIdx].y);
        }
    }

    static double CalcLen(Point* m, Point* n)
    {
        double x = m->x - n->x;
        double y = m->y - n->y;

        return sqrt(x*x+y*y);
    }

    int IsLenSatisfied(int bobIdx, int interestIdx)
    {
        double bobLen, dogLen1, dogLen2;

        if(g_len[bobIdx][interestIdx] == -1)
        {
            bobLen = CalcLen(&g_Bob.pos[bobIdx], &g_Bob.pos[bobIdx+1]);
            dogLen1 = CalcLen(&g_Bob.pos[bobIdx], &g_interests.pos[interestIdx]);
            dogLen2 = CalcLen(&g_Bob.pos[bobIdx+1], &g_interests.pos[interestIdx]);
            g_len[bobIdx][interestIdx] = ((bobLen*DOG_SPEED) >= (dogLen1+dogLen2)) ? 1 : 0;
        }
        return g_len[bobIdx][interestIdx];
    }

    BOOL DogFinding(int bobIdx)
    {
        int interestIdx;

        for(interestIdx = 0; interestIdx < g_interests.num; interestIdx++)
        {
            if(!g_isOccupied[interestIdx] && IsLenSatisfied(bobIdx, interestIdx))
            {
                g_isOccupied[interestIdx] = TRUE;
                if(g_selectIdx[interestIdx] == -1 || DogFinding(g_selectIdx[interestIdx]))
                {
                    g_selectIdx[interestIdx] = bobIdx;
                    g_BobToInterest[bobIdx] = interestIdx;
                    return TRUE;
                }
            }
        }

        return FALSE;
    }

    void Proc()
    {
        int bobIdx;
        for(bobIdx = 0; bobIdx < g_Bob.num-1; bobIdx++)
        {
            memset(g_isOccupied, 0, sizeof(g_isOccupied));
            if(DogFinding(bobIdx)) g_selectNum++;
        }
    }

    int main()
    {
        Input();
        Proc();
        Output();
        return 0;
    }