UVA 670 - The dog task

670 - The dog task

Bob喜歡跟他的狗一起散步，但狗狗跑得比較快，所以狗狗會在散步的過程中跑到其他有趣的地方，只要在每個會合點跟Bob相遇就好了。狗狗的速度是Bob的兩倍，而在兩個會合點之間狗狗頂多只能去一個有趣的地方。

輸入的第一行是有幾筆資料，每筆開頭給兩個數字(<=100)，第一個n是Bob會經過多少個會合點，第二個m是地圖上有多少有趣的地方。
接下來第一行是每個會合點的座標，下一行是有趣的點的座標。(最標是絕對值<=1000的int)

輸出先輸出狗狗總共會經過幾個點(會合點+有趣的點)，下一行是照順序印出他經過的座標。這個題目可能有多種答案，每一種都可以。

Sample Input 

1

4 5
1 4 5 7 5 2 -2 4
-4 -2 3 9 1 2 -1 3 8 -3

Sample Output 

6
1 4 3 9 5 7 5 2 1 2 -2 4

想法

簡單的說就是個二分匹配的題目，每個會合點配對一個有趣點(記得最後一個沒有)。
其實題目根本沒什麼，但卻WA了好幾次......
最後發現的問題真的很令人困惑，竟然是出在比較距離的地方，我一開始沒有開根號。
像這樣：
int dis(int a,int b,int c,int d){
    int xx=x[a][b]-x[c][d];
    int yy=y[a][b]-y[c][d];
    return xx*xx+yy*yy;
}
結果加了sqrt後就AC了.....但是這根本不合理啊啊啊！直接用平方比較應該比浮點運算更沒有誤差，而且題目的座標在1000以內，應該也不會有overflow的問題才對啊！

總之是謎啊......

#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int n,m,x[2][110],y[2][110];
bool select[110];
int match[2][110]={0};

double dis(int a,int b,int c,int d){
    int xx=x[a][b]-x[c][d];
    int yy=y[a][b]-y[c][d];
    return sqrt(xx*xx+yy*yy);
}

bool reach(int a,int b)
{
    if(2*dis(0,a+1,0,a)>=dis(1,b,0,a)+dis(0,a+1,1,b))return true;
    else return false;
}

bool find(int no)
{
    int i;
    for(i=1;i<=m;i++){
        if(select[i])continue;
        if(!reach(no,i))continue;
        select[i]=true;
        if(match[1][i]==0){
            match[0][no]=i; match[1][i]=no;
            return true;
        }
        else {
            if(find(match[1][i])){
                match[0][no]=i; match[1][i]=no;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int N,t,ans,i,j;
    scanf("%d",&N);
    for(t=1;t<=N;t++){
        scanf("%d %d",&n,&m);
        memset(match,0,sizeof(match));
        ans=0;
        for(i=1;i<=n;i++){
            scanf("%d %d",&x[0][i],&y[0][i]);
        }
        for(i=1;i<=m;i++){
            scanf("%d %d",&x[1][i],&y[1][i]);
        }
        for(j=1;j<n;j++){
            memset(select,false,sizeof(select));
            if(find(j)){
                ans++;
            }
        }
        printf("%d\n",n+ans);
        for(i=1;i<=n;i++){
            printf("%d %d",x[0][i],y[0][i]);
            if(match[0][i]!=0){
                printf(" %d %d",x[1][match[0][i]],y[1][match[0][i]]);
            }
            if(i!=n)printf(" ");
        }
        printf("\n");
        if(t<N)printf("\n");
    }
    return 0;
}