[UVa] 10080 Gopher II

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
struct Point{
    double x;
    double y;
};

bool edge[105][105];
int llink[105], rlink[105];
bool used[105];
bool DFS(int now, const int &m);

int main(int argc, char ** argv)
{
    system(argv[0]);
    int n, m, s, v;
    Point gopher[105], hole[105];
    while (scanf("%d %d %d %d", &n, &m, &s, &v) == 4) {
        // Input
        for (int i = 0; i < n; ++i) scanf("%lf %lf", &gopher[i].x, &gopher[i].y);
        for (int i = 0; i < m; ++i) scanf("%lf %lf", &hole[i].x, &hole[i].y);
        // Distance
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                double dis = sqrt(pow(gopher[i].x-hole[j].x,2)+pow(gopher[i].y-hole[j].y,2));
                if (dis/v <= s) edge[i][j] = true;
                else edge[i][j] = false;
            }

        // Bipartite
        int ans = 0;
        std::fill(llink, llink+n, -1);
        std::fill(rlink, rlink+m, -1);
        for (int i = 0; i < n; ++i) {
            std::fill(used, used+m, false);
            if (DFS(i, m)) ++ans;
        }
        printf("%d\n", n-ans);
    }
}
bool DFS(int now, const int &m)
{
    for (int nxt = 0; nxt < m; ++nxt) {
        if (edge[now][nxt] == false || used[nxt]) continue;

        used[nxt] = true;
        if (rlink[nxt] == -1 || DFS(rlink[nxt], m)) {
            llink[now] = nxt;
            rlink[nxt] = now;
            return true;
        }
    }
    return false;
}