「ROI 2017 Day 1」虎 (计算几何)

题意：（交互题）

已知$n$个点，$m$次询问，每次询问交互器随机生成一个位置的关键点，要求在$k$次查询中给出一个合法解

查询：一个凸包，返回关键点是否在凸包中

解：一个凸包，包含关键点，且不包含其它点，保证有界

对关键点的包含是包括了边界线的，其它点的包含不包括边界线，凸包均要按照顺时针给出

Solution 1 （未完全实现）

先将给定点分层转化为若干凸包，容易通过二分得到关键点所在的层

如果关键点以内不再有凸包，显然得到一个解

否则，一个合法的解一定是在两层凸包中某一层选取两个点，另一层选取一个点得到的三角形

先考虑内层选两个点的情况，令二分边界为内层凸包上点的编号，$l,r$

考虑实现一个操作，对于$l,r$，找到其连接的直线在顺时针方向上在外层凸包上切到的段

由此得到一个凸包进行查询，即可进行二分，最终$l+1=r$时，再进行一次上述操作得到一组解（不一定合法）

如果不合法，同理再在外层上二分一次

最终写道第一种情况弃掉了。。。

Solution2 随机分裂

良好的随机分裂可以跑到max query times<=33的好成绩

考虑一个非常简单的剖开$n$个点的方法：

1.找到这些点的凸包，从点集中删掉

2.从剩余点中选择一个作为中心，分别与凸包上的点连边，将平面分开

3.确定每个三角形中包含的点，加上三个顶点，继续进行剖分

最终当凸包以外不再有点时，结束

查询也是比较显然的：

对于当前凸包及其中心，二分找到关键点对应的位置，然后继续进行，直到不存在中心

二分方法：

凸包构成一圈，取一个点为$l$，顺时针180以内的范围最大角度的点为$r$，每次将中心和$l,mid$这连续一段查询判断是否包含

这样存在的问题是：可能不在$l$的180范围内，需要在开始二分前判断一下

十分朴素的实现也可以获得90分的好成绩

优化：

每次选取中心时，多随机几次，估价找到一个最优剖分即可

Loj Submission -包含大量调试语句和内嵌的交互部分

Loj Submission

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T& a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T& a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

bool Mbe;
const int N=5010;

int n,q;

// 计算几何部分
namespace Geometry{
struct Node{
	ll x,y;
	Node(){ }
	Node(ll x,ll y):x(x),y(y){ }
	Node operator - (const Node __) const { return Node(x-__.x,y-__.y); }
	Node operator + (const Node __) const { return Node(x+__.x,y+__.y); }
	ll operator ^ (const Node __) const { return 1ll*x*__.y-1ll*y*__.x; }
	bool operator == (const Node __) const { return x==__.x && y==__.y; }
	void Read(){ x=rd(),y=rd(); }
} A[N],QuePoint;
typedef vector <int> V;
// check close wise
int chk(int i,int j,int k,int bound=0){ return ((A[k]-A[i])^(A[j]-A[i]))>=bound; }
int chk(Node i,int j,int k,int bound=0){ return ((A[k]-i)^(A[j]-i))>=bound; }
// this is clockwise
int CheckConvex(const V &P){
	int n=P.size();
	rep(i,0,n-1) {
		int j=(i+1)%n,k=(j+1)%n;
		if(!chk(P[j],P[k],P[i])) return 0;
	}
	return 1;
}
// this is clock-wise
int CheckIn(const V&P,Node X,int bound=0){
	rep(i,0,P.size()-1) {
		int j=(i+1)%P.size();
		if(chk(X,P[i],P[j],bound)) continue;
		return 0;
	}
	return 1;
}
int Check(V P){
	if(P.size()<=2) return 0;
	printf("? %llu ",P.size());
	for(int i:P) printf("%d ",i); 
	puts("");
	fflush(stdout);
	static char s[5]; scanf("%s",s);
	return *s=='Y';
}
void Output(V P){
	printf("! %llu ",P.size());
	for(int i:P) printf("%d ",i);
	puts("");
	fflush(stdout);
}
V Convex(V P){
	if(P.size()<=2) return P;
	V Ans;
	int n=P.size();
	static int I[N],mk[N],S[N],T;
	rep(i,0,n-1) mk[I[P[i]]=i]=0;
	sort(P.begin(),P.end(),[&](int x,int y){ return A[x].x<A[y].x || (A[x].x==A[y].x && A[x].y>A[y].y); });
	T=0;
	rep(i,0,n-1) {
		while(T>1 && ((A[P[i]]-A[S[T]])^(A[S[T-1]]-A[S[T]]))>0 ) T--;
		S[++T]=P[i];
	}
	rep(i,1,T) Ans.pb(S[i]),mk[I[S[i]]]=1;
	sort(P.begin(),P.end(),[&](int x,int y){ return A[x].x<A[y].x || (A[x].x==A[y].x && A[x].y<A[y].y); });
	T=0;
	rep(i,0,n-1) {
		while(T>1 && ((A[P[i]]-A[S[T]])^(A[S[T-1]]-A[S[T]]))<0 ) T--;
		S[++T]=P[i];
	}
	drep(i,T,1) if(!mk[I[S[i]]]) Ans.pb(S[i]);
	return Ans;
}
}
using namespace Geometry;


const int M=2e5+10;

V C[M],S[M];
int K[M],D[M],E[M],rt,m,mk[M];
// 剖分
// C凸包，S子节点
// K中心，D凸包上0号点对应的180范围内的最大点，E凸包上D号点对应180范围内的最大点
// m个数
void Build(int &u,V P) {
	sort(P.begin(),P.end());
	int n=P.size();
	C[u=++m]=Convex(P);
	rep(i,0,n-1) mk[i]=0;
	if(C[u].size()==P.size()) return;
	for(int i:C[u]) mk[lower_bound(P.begin(),P.end(),i)-P.begin()]=1;
	V T; rep(i,0,n-1) if(!mk[i]) T.pb(P[i]);
	n=C[u].size();
    // 获取剖分结果
	auto Get=[&]() {
		if(rand()&1) K[u]=T[(T.size()/(rand()%3+2)+rand()%8)%T.size()];
		else K[u]=T[rand()%T.size()];
		V P=T; P.erase(lower_bound(P.begin(),P.end(),K[u]));
		D[u]=E[u]=0;
		while(D[u]<n-1 && chk(K[u],C[u][0],C[u][D[u]+1])) D[u]++;
		E[u]=D[u];
		while(E[u]<n-1 && chk(K[u],C[u][D[u]],C[u][E[u]+1])) E[u]++;
		vector <V> ST(n);
		for(int x:P) {
			rep(i,0,n-1) {
				if(chk(K[u],C[u][i],x) && chk(K[u],x,C[u][(i+1)%n])) {
					ST[i].pb(x);
					break;
				}
			}
		}
		rep(i,0,n-1) ST[i].pb(K[u]),ST[i].pb(C[u][i]),ST[i].pb(C[u][(i+1)%n]);
		return ST;
	};
	vector <V> st;
	int mi=1e9;
	rep(kase,1,5) {
		int d=D[u],e=E[u],k=K[u];
		auto ST=Get();
		int now=0;
		for(V j:ST) cmax(now,(int)j.size());
		if(now>mi){ D[u]=d,E[u]=e,K[u]=k; continue; }
		st=ST,mi=now;
	}
	rep(i,0,n-1) {
		int x; Build(x,st[i]);
		S[u].pb(x);
	}
}

void Init() {
	V T(n);
	rep(i,0,n-1) T[i]=i+1;
	Build(rt,T);
}

void Find(int u=rt){
	if(!S[u].size()) return Output(C[u]);
	int n=C[u].size();
	int l,r;
	auto Get=[&](int l,int r) {
		V T; T.pb(K[u]);
		l%=n,r%=n;
		for(int i=l;;i=(i+1)%n) {
			T.pb(C[u][i]);
			if(i==r) break;
		}
		return Check(T);
	};
	if(Get(0,D[u])) l=0,r=D[u];
	else if(Get(D[u],E[u])) l=D[u],r=E[u];
	else l=E[u],r=n;
	while(l+1<r) {
		int mid=(l+r)>>1;
		if(Get(l,mid)) r=mid;
		else l=mid;
	}
	Find(S[u][l]);
}

int main(){ 
	n=rd();
	rep(i,1,n) A[i].Read();
	Init();
	q=rd();
	rep(_,1,q) Find();
}