1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include<bitset>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
using uni=unsigned;
using ll=long long;
using db=double;
const int N=21,M=410,FSIZE=1<<24,INF=0x7f7f7f7f;
int n,m;
bitset<M> t[(1<<21)-1];
bitset<N> b[(1<<21)-1];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
bool f=1;
for(;48>*InF||*InF>57;f^=*InF++=='-');
for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
x=f?x:-x;
}
struct point{
db x,y;
bool operator==(point b){return(x==b.x&&y==b.y);}
bool operator!=(point b){return(x!=b.x||y!=b.y);}
db operator*(point b){return(x*b.x+y*b.y);}
};
struct line{
point a,b;
point operator&(line y){
db t=((a.x-y.a.x)*(y.a.y-y.b.y)-(a.y-y.a.y)*(y.a.x-y.b.x))
/((a.x-b.x)*(y.a.y-y.b.y)-(a.y-b.y)*(y.a.x-y.b.x));
return((point){a.x+(b.x-a.x)*t,a.y+(b.y-a.y)*t});
}
};
point a[N],p[N<<2];
bool check(point x,int l,int r,point t){
if(t==p[l]||t==p[r]) return(0);
auto q=(line){p[l],p[r]}&(line){x,t};
return(
min(p[l].x,p[r].x)<=q.x&&q.x<=max(p[l].x,p[r].x)&&
min(p[l].y,p[r].y)<=q.y&&q.y<=max(p[l].y,p[r].y)&&
min(x.x,t.x)<=q.x&&q.x<=max(x.x,t.x)&&
min(x.y,t.y)<=q.y&&q.y<=max(x.y,t.y));
}
bool can(point x,point y){
for(int i=0;i<m<<2;i+=4){
if(check(x,i,i+1,y)) return(0);
if(check(x,i+1,i+2,y)) return(0);
if(check(x,i+2,i+3,y)) return(0);
if(check(x,i+3,i,y)) return(0);
}
if(x.x==y.x)
for(int i=0;i<m<<2;++i)
if(p[i]!=y&&p[i].x==x.x&&min(x.y,y.y)<=p[i].y&&p[i].y<=max(x.y,y.y)) return(0);
if(x.y==y.y)
for(int i=0;i<m<<2;++i)
if(p[i]!=y&&p[i].y==x.y&&min(x.x,y.x)<=p[i].x&&p[i].x<=max(x.x,y.x)) return(0);
return(1);
}
void work(){
read(n);read(m);
for(int i=1;i<=n;++i){
t[1<<(i-1)].reset();
b[1<<(i-1)].reset();
read(a[i].x);read(a[i].y);
}
for(int i=0;i<m;++i){
read(p[i<<2].x);read(p[i<<2].y);
read(p[(i<<2)+1].x);read(p[(i<<2)+1].y);
read(p[(i<<2)+2].x);read(p[(i<<2)+2].y);
read(p[(i<<2)+3].x);read(p[(i<<2)+3].y);
}
for(int i=1;i<=n;++i)
for(int j=0;j<m<<2;++j)
t[1<<(i-1)][j]=can(a[i],p[j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j) b[1<<(i-1)][j]=can(a[i],a[j]);
int ans=0x7fffffff;
for(int i=1;i<1<<n;++i)
if(__builtin_popcount(i)<ans){
b[i]=b[i&(i-1)]|b[i&-i];
if((t[i]=t[i&(i-1)]|t[i&-i]).count()==m<<2){
bool all=1;
for(int j=i;j;j&=j-1)
if(!b[i][__builtin_ffs(j)]){
all=0;
break;
}
if(all&&__builtin_popcount(i)>1) ans=__builtin_popcount(i);
}
}
if(ans==0x7fffffff)
printf("No Solution!\n");
else
printf("%d\n",ans);
}
int main(){
fread(BuF,1,FSIZE,stdin);
int t;
for(read(t);t--;work());
fclose(stdin);
fclose(stdout);
return(0);
}
|