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

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

「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

#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();
}