ZOJ 3156 Taxi （二分匹配+二分查找）

ZOJ 3156 Taxi （二分匹配+二分查找）

題目鏈接：Taxi

As we all know, it often rains suddenly in Hangzhou during summer time.I suffered a heavy rain when I was walking on the street yesterday, so I decided to take a taxi back school. I found that there were n people on the street trying to take taxis, and m taxicabs on the street then. Supposing that the cars waited still and each person walked at a speed of v, now given the positions of the n persons and the m taxicabs, you should find the minimum time needed for all the persons to get on the taxicabs. Assume that no two people got on the same taxicab.

Input

For each case, you are given two integers 0 <= n <= 100 and n< = m <= 100 on the first line, then n lines, each has two integers 0 <= Xi, Yi <= 1000000 describing the position of the ith person, then m lines, each has two integers 0 <= xi, yi< = 1000000 describing the position the ith taxicab, then a line has a float 0.00001 < v <= 10000000 which is the speed of the people.

Output

You shuold figue out one float rounded to two decimal digits for each case.

Sample Input

2 3
0 0
0 1
1 0
1 1
2 1
1

Sample Output

1.00

題意：n個人，m輛車，任何是n個人的坐標，和m個車的坐標，計算所有人上車所用的最少時間

錯了5遍，dis數組開小了。。。

#include 
#include 
#include 
#include 
#include 
#include 
#define init(a) memset(a,0,sizeof(a))
#define PI acos(-1,0)
using namespace std;
const int maxn = 110;
const int maxm = 10010;
#define lson left, m, id<<1
#define rson m+1, right, id<<1|1
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b

int n,m;
bool vis[maxn];
int line[maxn];
double ma[maxn][maxn];
struct node
{
    double x,y;
};
node g[maxn],h[maxn];
double dis[maxm],st;

int cmp(const void *a,const void *b)
{
    return (*(double *)a > *(double *)b) ? 1 : -1;
}

int DFS(int u)
{
    for(int v = 1; v <= m; v++)
    {
        if (ma[u][v]<=st && !vis[v])
        {
            vis[v] = 1;
            if (line[v]== -1 || DFS(line[v]))
            {
                line[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int K_M()
{
    memset(line,-1,sizeof line);
    for (int i=1; i<=n; i++)
    {
        init(vis);
        if (DFS(i)==0)
            return 0;
    }
    return 1;
}
int ans;
void B_search(int num)
{
    int low = 0;
    int high = num - 1;

    while (low <= high)
    {
        //printf("low = %d   high = %d\n",low,high);
        //printf("mid = %d",mid);
        int mid = (low + high)/2;
        st = dis[mid];
        //printf("st = %.2lf\n",st);
        //printf("ans = %lf\n",ans);
        if ( K_M()==1 )
        {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
}
int main()
{
    double v;
    int num = 0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init(ma);
        num = 0;
        for (int i=1; i<=n; i++)
            scanf("%lf%lf",&g[i].x,&g[i].y);
        /*for(int i = 1;i<=n;i++)
        printf("g.x = %lf g.y = %lf\n",g[i].x,g[i].y);*/

        for (int i=1; i<=m; i++)
            scanf("%lf%lf",&h[i].x,&h[i].y);

            /*for(int i = 1;i<=n;i++)
        printf("h.x = %lf h.y = %lf\n",h[i].x,h[i].y);*/

        scanf("%lf",&v);

        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=m; j++)
            {
                ma[i][j] = (sqrt((g[i].x-h[j].x)*(g[i].x-h[j].x)+(g[i].y-h[j].y)*(g[i].y-h[j].y))/v);
                dis[num++] = ma[i][j];

                //printf("ma[i][j] = %lf\n",ma[i][j]);

            }
        }
        qsort(dis,num,sizeof(dis[0]),cmp);
        /*for(int i = 0;i