Algorithm :
1. Add source and sink nodes.
2. Add link from source to PERSONi node.
3. Add link from TAXIi to sink node.
4. Add a link from Pi to Ti if it is possible for the taxi to cover the block distance between itself and the person within the given time.
5. Run Dinic's algorithm to compute the maxflow.
Source:
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
public class TAXI {
static final int INF = 0x7fffffff;
int maxnodes, maxedges, src, dest, edges;
int[] top, work, Q;
int[] head, prev, flow, cap, dist;
boolean marked;
public void init(int maxnodes, int maxedges) {
this.maxnodes = maxnodes;
this.maxedges = maxedges;
top = new int[maxnodes];
work = new int[maxnodes];
Q = new int[maxnodes];
dist = new int[maxnodes];
head = new int[maxedges];
prev = new int[maxedges];
flow = new int[maxedges];
cap = new int[maxedges];
clear();
}
public void clear() {
Arrays.fill(top, -1);
edges = 0;
}
public void addEdge(int u, int v, int capacity) {
head[edges] = v;
cap[edges] = capacity;
flow[edges] = 0;
prev[edges] = top[u];
top[u] = edges++;
head[edges] = u;
cap[edges] = 0;
flow[edges] = 0;
prev[edges] = top[v];
top[v] = edges++;
}
boolean dinic_bfs() {
Arrays.fill(dist, -1);
dist[src] = 0;
int sizeQ = 0;
Q[sizeQ++] = src;
for (int i = 0; i < sizeQ; ++i) {
int u = Q[i];
for (int e = top[u]; e >= 0; e = prev[e]) {
int v = head[e];
if (flow[e] < cap[e] && dist[v] < 0) {
dist[v] = dist[u] + 1;
Q[sizeQ++] = v;
}
}
}
return dist[dest] >= 0;
}
int dinic_dfs(int u, int f) {
if (u == dest) {
return f;
}
for (int e = work[u]; e >= 0; work[u] = e = prev[e]) {
int v = head[e];
if (flow[e] < cap[e] && dist[v] == dist[u] + 1) {
int df = dinic_dfs(v, Math.min(f, cap[e] - flow[e]));
if (df > 0) {
flow[e] += df;
flow[e^1] -= df;
return df;
}
}
}
return 0;
}
public int maxFlow(int src, int dest) {
this.src = src;
this.dest = dest;
int flow = 0;
while (dinic_bfs()) {
System.arraycopy(top, 0, work, 0, maxnodes);
while (true) {
int df = dinic_dfs(src, INF);
if (df == 0) {
break;
}
flow += df;
}
}
return flow;
}
static class Point{
int x, y;
Point(int a, int b){
x = a; y = b;
}
int distTo(Point b){
return Math.abs(this.x-b.x)+Math.abs(this.y-b.y);
}
}
public static void main(String[] args){
int nCases = IO.nextInt();
TAXI instance = new TAXI();
instance.init(400+200+2, 2*(400+200+400*200));
while(nCases-->0){
instance.clear();
int a, b, c, d;
a = IO.nextInt();
b = IO.nextInt();
c = IO.nextInt();
d = IO.nextInt();
int sourceI = 0, sinkI = a+b+1;
Point[] persons = new Point[a];
Point[] taxis = new Point[b];
for(int i=0;i<a;++i){
int x, y;
x = IO.nextInt();
y = IO.nextInt();
persons[i] = new Point(x, y);
instance.addEdge(sourceI, i+1, 1);
}
int maxSteps = (c*d)/200;
for(int i=0;i<b;++i){
int x, y;
x = IO.nextInt();
y = IO.nextInt();
taxis[i] = new Point(x, y);
instance.addEdge(a+i+1, sinkI, 1);
for(int i2=0;i2<persons.length;++i2){
int dist = taxis[i].distTo(persons[i2]);
if(dist<=maxSteps){
instance.addEdge(i2+1, a+i+1, 1);
}
}
}
IO.println(instance.maxFlow(sourceI, sinkI));
}
}
private static class IO {
private static InputStream stream = System.in;
private static byte[] buf = new byte[1024];
private static int curChar, numChars;
private static int read() {
if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public static int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public static char nextChar() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
return (char) c;
}
private static boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private static void println(Object... a) {
for (Object o : a) {
System.out.print(o);
}
System.out.println();
}
}
}
