题意：
给出一个由n个点组成的凸包，以及凸包内的k个点，问是否能够在凸包上选择最多2k个点构造一个新的
凸包，使得新的凸包覆盖原来的k个点。
要求2k个点覆盖原本的k个点，只要对原k个点构造凸包，然后选择该凸包内一点O与该凸包的顶点连一条射线，其
与大凸包相交的边的两端点即为要保留的点，小凸包的顶点个数<=k，所有结果最后一定存在。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<set> 7 #include<map> 8 #include<stack> 9 #include<time.h> 10 #include<cstdlib> 11 #include<cmath> 12 #include<list> 13 using namespace std; 14 #define MAXN 100100 15 #define eps 1e-7 16 #define For(i,a,b) for(int i=a;i<=b;i++) 17 #define Fore(i,a,b) for(int i=a;i>=b;i--) 18 #define lson l,mid,rt<<1 19 #define rson mid+1,r,rt<<1|1 20 #define mkp make_pair 21 #define pb push_back 22 #define cr clear() 23 #define sz size() 24 #define met(a,b) memset(a,b,sizeof(a)) 25 #define iossy ios::sync_with_stdio(false) 26 #define fre freopen 27 #define pi acos(-1.0) 28 #define inf 1e9+9 29 #define Vector Point 30 const int Mod=1e9+7; 31 typedef unsigned long long ull; 32 typedef long long ll; 33 int dcmp(double x){ 34 if(fabs(x)<=eps) return 0; 35 return x<0?-1:1; 36 } 37 double ox,oy; 38 struct Point{ 39 double x,y,id; 40 Point(){} 41 Point(double x,double y):x(x),y(y) {} 42 bool operator < (const Point &a)const { if(x==a.x) return y<a.y; return x<a.x; } 43 Point operator - (const Point &a)const{ return Point(x-a.x,y-a.y); } 44 Point operator + (const Point &a)const{ return Point(x+a.x,y+a.y); } 45 Point operator * (const double &a)const{ return Point(x*a,y*a); } 46 Point operator / (const double &a)const{ return Point(x/a,y/a); } 47 void read(){ scanf("%lf%lf",&x,&y); } 48 bool operator == (const Point &a)const{ return dcmp(x-a.x)==0 && dcmp(y-a.y)==0; } 49 }; 50 double Dot(Vector a,Vector b) { return a.x*b.x+a.y*b.y; } 51 ll dis(Vector a) { return sqrt(Dot(a,a)); } 52 double Cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; } 53 int ConvexHull(Point *p,int n,Point *ch){ 54 sort(p+1,p+1+n); 55 int m=0; 56 For(i,1,n){ 57 while(m>1 && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; 58 ch[m++]=p[i]; 59 } 60 int k=m; 61 Fore(i,n-1,1) { 62 while(m>k && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; 63 ch[m++]=p[i]; 64 } 65 if(n>1) m--; 66 return m; 67 } 68 Point getInsect(Point p,Vector v,Point q,Vector w) { 69 Vector u=p-q; 70 double t=Cross(w,u)/Cross(v,w); 71 return p+v*t; 72 } 73 Point p[200005],pp[200005],ch[200005],o; 74 bool chk(Point p1,Point p2,Point q1,Point q2) { 75 double c1=Cross(p2-p1,q1-p1),c2=Cross(p2-p1,q2-p1); 76 double c3=Dot(p2-p1,q1-p1),c4=Dot(p2-p1,q2-p1); 77 if(dcmp(c1)*dcmp(c2)<0) { 78 Point cp=getInsect(p1,p2-p1,q1,q2-q1); 79 return Dot(cp-p1,p2-p1)>0; 80 } 81 return 0; 82 } 83 int n,k,res; 84 set<int>ans; 85 void solve(){ 86 ans.clear(); 87 scanf("%d",&n); 88 For(i,0,n-1) p[i].read(); 89 scanf("%d",&k); 90 For(i,1,k) pp[i].read(); 91 int m=ConvexHull(pp,k,ch); 92 o=ch[0]; 93 For(i,1,m-1) o=(o+ch[i])/2; 94 res=0; 95 For(i,0,m-1) { 96 while(!chk(o,ch[i],p[res],p[(res+1)%n])) res=(res+1)%n; 97 ans.insert(res);ans.insert((res+1)%n); 98 } 99 set<int>::iterator it; 100 cout<<"Yes"<<endl; 101 cout<<ans.sz<<endl; 102 for(it=ans.begin();it!=ans.end();it++){ 103 if(it!=ans.begin()) printf(" "); 104 printf("%d",(*it)+1); 105 } 106 cout<<endl; 107 } 108 int main(){ 109 // fre("in.txt","r",stdin); 110 int t=1; 111 cin>>t; 112 For(i,1,t) solve(); 113 return 0; 114 }