1 /*--------------------------------------------------------------------------------------*/  2   3 #include <algorithm>  4 #include <iostream>  5 #include <cstring>  6 #include <ctype.h>  7 #include <cstdlib>  8 #include <cstdio>  9 #include <vector> 10 #include <string> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <set> 15 #include <map> 16  17 //debug function for a N*M array 18 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++) 19 {for(int j=0;j<(M);j++){ 20 printf("%d",G[i][j]);}printf("\n");} 21 //debug function for int,float,double,etc. 22 #define debug_var(X) cout<<#X"="<<X<<endl; 23 #define LL long long 24 const int INF = 0x3f3f3f3f; 25 const LL LLINF = 0x3f3f3f3f3f3f3f3f; 26 /*--------------------------------------------------------------------------------------*/ 27 using namespace std; 28  29 int N,M,T,t; 30 const int maxn = 6010; 31 vector <int> G[maxn]; 32 int uN; 33 int Mx[maxn],My[maxn]; 34 int dx[maxn],dy[maxn]; 35 int dis; 36 bool used[maxn]; 37 bool SearchP() 38 { 39     queue<int> Q; 40     dis = INF; 41     memset(dx,-1,sizeof dx); 42     memset(dy,-1,sizeof dy); 43     for(int i=1;i<=uN;i++) 44     { 45         if(Mx[i] == -1) 46         { 47             Q.push(i); 48             dx[i] = 0; 49         } 50     } 51     while(!Q.empty()) 52     { 53         int u = Q.front(); 54         Q.pop(); 55         if(dx[u] > dis) break; 56         int sz = G[u].size(); 57         for(int i=0;i<sz;i++) 58         { 59             int v = G[u][i]; 60             if(dy[v] == -1) 61             { 62                 dy[v] = dx[u] + 1; 63                 if(My[v] == -1) dis = dy[v]; 64                 else 65                 { 66                     dx[My[v]] = dy[v] + 1; 67                     Q.push(My[v]); 68                 } 69             } 70         } 71     } 72     return dis != INF; 73 } 74 bool DFS(int u) 75 { 76     int sz = G[u].size(); 77     for(int i=0;i<sz;i++) 78     { 79         int v = G[u][i]; 80         if(!used[v] && dy[v] == dx[u]+1) 81         { 82             used[v] = true; 83             if(My[v] != -1 && dy[v] == dis) continue; 84             if(My[v] == -1 || DFS(My[v])) 85             { 86                 My[v] = u; 87                 Mx[u] = v; 88                 return true; 89             } 90         } 91     } 92     return false; 93 } 94  95 int MaxMatch() 96 { 97     int res = 0; 98     memset(Mx,-1,sizeof Mx); 99     memset(My,-1,sizeof My);100     while(SearchP())101     {102         memset(used,false,sizeof used);103         for(int i=1;i<=uN;i++) if(Mx[i] == -1 && DFS(i))104             res++;105     }106     return res/2;107 }108 109 typedef pair<int,int> point;110 vector <point> gst;111 int v[maxn];112 113 int main()114 {115     scanf("%d",&T);116     int cas = 0;117     while(T--)118     {119         scanf("%d%d",&t,&N);120         for(int i=0;i<maxn;i++) G[i].clear();121 122         gst.clear();123         for(int i=1,x,y,s;i<=N;i++)124         {125             scanf("%d%d%d",&x,&y,&s);126             gst.push_back(make_pair(x,y));127             v[i] = s;128         }129         scanf("%d",&M);130         uN = N+M;131         for(int i=1,x,y;i<=M;i++)132         {133             scanf("%d%d",&x,&y);134             for(int g=0;g<gst.size();g++)135             {136                 if((x-gst[g].first)*(x-gst[g].first)+(y-gst[g].second)*(y-gst[g].second) <= t*v[g+1]*t*v[g+1])137                 {138                     G[g+1].push_back(i+N);139                     G[i+N].push_back(g+1);140                     //printf("link:[%d,%d]\n",g+1,i+N);141                 }142             }143         }144         printf("Scenario #%d:\n%d\n\n",++cas,MaxMatch());145     }146 }