【FJOI2015】最小覆盖双圆问题(坐标旋转)(二分)(最小圆覆盖)

传送门

发现可以在 xxx 方向找到一个点 midmidmid ,使得 [1,mid],[mid+1,r][1,mid],[mid+1,r][1,mid],[mid+1,r] 的点分别用一个圆来覆盖

然后可以二分 + 最小圆覆盖来解决

但这样显然是错的,因为划分可能不沿 xxx 轴,于是我们可以将坐标轴旋转

考虑 n1000n\le 1000n≤1000,加上二分,数据组数,大概可以旋转个 100100100 次,每种旋转求一次即可


顺便一提最小圆覆盖:

考虑增量法:
假设当前加入第 iii 个点,前 i1i-1i−1 个点求出的圆是 Ci1C_{i-1}Ci−1​
如果 iii 在圆中,那么可以跳过,如果 iii 不在圆中,那么 iii 一定在圆上
于是我们固定 iii 点,枚举 jjj,假设当前加入 jjj 点,前 j1j-1j−1 个点求出的最小圆是 Ci,j1C_{i,j-1}Ci,j−1​
如果 jjj 在圆中那么可以跳过,否则 jjj 一定在圆上,这个时候我们以 i,ji,ji,j 为直径作圆
这个圆 Ci,jC_{i,j}Ci,j​ 不一定包涵 [1,j1][1,j-1][1,j−1] 的点,于是我们继续枚举 k[1,j1]k\in [1,j-1]k∈[1,j−1],如果 kkk 不在圆中那么 kkk 在圆上,三点定圆,这样求出的圆一定包涵 {i}[1,j]\{i\}\cup[1,j]{i}∪[1,j] 的所有点
考虑复杂度,jjj 这一步是要枚举满的,但是进入 kkk 的循环当且仅当 jjj 在圆上,概率为 3/j3/j3/j
iii 个点不在圆中的概率是 3/i3/i3/i,这个时候才会进入 jjj,于是复杂度为 O(n)O(n)O(n)

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int N = 1e3 + 5;
cs double eps = 1e-8, PI = acos(-1.0);
cs double angle = PI/100, si=sin(angle), co=cos(angle);
cs double INF = 1e9;
int sgn(double a){ if(fabs(a)<eps) return 0; return a<0?-1:1; }
struct P{
	double x,y; P(double _x=0, double _y=0){ x=_x; y=_y; }
	friend P operator + (cs P &a, cs P &b){ return P(a.x+b.x,a.y+b.y); }
	friend P operator - (cs P &a, cs P &b){ return P(a.x-b.x,a.y-b.y); }
	friend double operator * (cs P &a, cs P &b){ return a.x*b.y-a.y*b.x; }
	P operator * (cs double &k){ return P(x*k, y*k); }
	double norm(){ return x*x+y*y; }
	P rot(){ return P(x*co-y*si, x*si+y*co); }
	bool operator < (cs P &a)cs{ return x<a.x; }
}p[N],q[N];

double dis(P a,P b){ return sqrt((a-b).norm()); }

struct Cir{
	P o; double r; Cir(){}
	Cir(cs P &_o, cs double &_r):o(_o),r(_r){}
	bool in(P a){ return r+eps>dis(a,o); }
}C;
int n; 
Cir getCir(P a,P b,P c){
	if(!sgn((a-b)*(b-c))){
		if(a.x==b.x){
			if((a.y<b.y)==(b.y<c.y)) return Cir((a+c)*0.5,dis(a,c)*0.5);
			if((a.y<c.y)==(c.y<b.y)) return Cir((a+b)*0.5,dis(a,b)*0.5);
			return Cir((b+c)*0.5,dis(b,c)*0.5);
		}
		else{
			if((a.x<b.x)==(b.x<c.x)) return Cir((a+c)*0.5,dis(a,c)*0.5);
			if((a.x<c.x)==(c.x<b.x)) return Cir((a+b)*0.5,dis(a,b)*0.5);
			return Cir((b+c)*0.5,dis(b,c)*0.5);
		}
	}
	double A=b.x-a.x,B=b.y-a.y,C=c.x-b.x,D=c.y-b.y,E=b.norm()-a.norm(),F=c.norm()-b.norm();
	P o(0.5*(B*F-D*E)/(B*C-A*D),0.5*(A*F-C*E)/(A*D-B*C)); 
	return Cir(o,dis(a,o));
}
double Solve(int l,int r){
	if(l>r) return 0; int n=0;
	for(int i=l;i<=r;i++) q[++n]=p[i];
	random_shuffle(q+1,q+n+1);
	C=Cir(q[1],0);
	for(int i=1;i<=n;i++) if(!C.in(q[i])){
		C.o=q[i]; C.r=0;
		for(int j=1; j<i; j++) if(!C.in(q[j])){
			C.o=(q[i]+q[j])*0.5;
			C.r=dis(C.o,q[i]);
			for(int k=1;k<j;k++) if(!C.in(q[k])) C=getCir(q[i],q[j],q[k]);
		} 
	} return C.r;
}
int main(){
	srand(time(0));
	while(scanf("%d",&n)&&n){
		double ans=INF;
		for(int i=1; i<=n; i++) scanf("%lf%lf",&p[i].x,&p[i].y);
		for(int T=0; T<100; T++){
			for(int i=1; i<=n; i++) p[i]=p[i].rot();
			sort(p+1, p+n+1);
			int l=1, r=n;
			while(l<=r){
				int mid=(l+r)>>1; double r1=Solve(1,mid),r2=Solve(mid+1,n);
				if(min(r1,r2)>=ans) break;
				ans = min(ans,max(r1,r2));
				if(r1>r2) r=mid-1; else l=mid+1;
			} 
		} printf("%.2lf\n", ans);
	} return 0;
}
【FJOI2015】最小覆盖双圆问题(坐标旋转)(二分)(最小圆覆盖)【FJOI2015】最小覆盖双圆问题(坐标旋转)(二分)(最小圆覆盖) FSYo 发布了614 篇原创文章 · 获赞 94 · 访问量 5万+ 他的留言板 关注
上一篇:left join加上where条件


下一篇:P2239 螺旋矩阵