#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int const N= 3010;
int dist[N<<1], mx[N], my[N], m, n;
vector<int> map[N];
int que[N<<1], rear, tail;
int bfs(){
rear= 0, tail= -1;
for( int i= 1; i<= n; ++i ){
if( mx[i]== -1 ) que[++tail]= i;
}
for( int i= 0; i<= n+ m; ++i ) dist[i]= 0;
int flag= 0;
while( rear<= tail ){
int u= que[rear++];
for( size_t i= 0; i< map[u].size(); ++i ){
int v= map[u][i];
if( dist[n+v]== 0 ){
dist[n+v]= dist[u]+ 1;
if( my[v]!= -1 ) {
dist[ my[v] ]= dist[n+ v]+ 1;
que[++tail]= my[v];
}
else flag= 1;
}
}
}
return flag;
}
int dfs( int u ){
for( size_t i= 0; i< map[u].size(); ++i ){
int v= map[u][i];
if( dist[u]+ 1== dist[v+ n] ){
int t= my[v];
dist[v+n]= 0;
if( t== -1 || dfs( t ) ){
my[v]= u; mx[u]= v;
return 1; }
}
}
return 0;
}
int solve(){
for( int i= 0; i<= n; ++i ) mx[i]= -1;
for( int i= 0; i<= m; ++i ) my[i]= -1;
int ans= 0;
while( bfs() ){
for( int i= 1; i<= n; ++i )
if( mx[i]== -1 && dfs(i) ) ans++;
}
return ans;
}
int t, ux[N], uy[N], gx[N], gy[N], speed[N];
int inline isok( int x1, int y1, int x2, int y2, int s ){
return sqrt( 1.0* (x1-x2)* (x1-x2)+ (y1-y2)* (y1-y2) )/ s<= 1.0* t;
}
void build(){
scanf("%d",&t );
scanf("%d",&n );
for( int i= 1; i<= n; ++i )
scanf("%d%d%d", gx+ i, gy+ i, speed+ i );
scanf("%d",&m );
for( int i= 1; i<= m; ++i )
scanf("%d%d", ux+ i, uy+ i );
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= m; ++j )
if( isok( gx[i], gy[i], ux[j], uy[j], speed[i] ) )
map[i].push_back( j );
}
int main(){
int test;
scanf("%d",&test );
for( int ca= 1; ca<= test; ++ca ){
build();
printf("Scenario #%d:\n%d\n\n", ca, solve() );
for( int i= 0; i<= n; ++i ) map[i].clear();
}
return 0;
}
|