「NOI2014模拟20」修路 - 计算几何+凸包+状压动规

题目大意

    大卫发现了一块新岛屿！他打算对此岛屿进行开发。在这个岛屿上，大卫打算建$N$个餐馆。第$i$个餐馆的坐标将是$(x_i,y_i)$。另外，大卫还将建造$K$条道路。路的位置还没有决定。路是一条直线。因为路很贵，他想要尽量使它们发挥作用。让$d_i$表示第$i$个餐馆与最近的道路间的距离。大卫想最小化$\max(d_1,d_2,\ldots,d_N)$。这也正是你的任务。

---

题目分析

发现$n,k$的范围很小，因此完全可以设置状态$f[S,i]$表示集合为$S$，使用了$i$条直线时的最大值的最小值。
那么我们就将问题转化为了求一个集合中仅用一条直线所能达到的最大值的最小值。
也就是要让点到一条直线的距离最大值最小化。（二分无卵用）
可以转化为点与该直线的法向量点积最大值最小化。
点积最大值显然在凸包上，故求出凸包暴力扫描即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
 
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=25,maxs=1<<13;

struct Point {
	int x,y;
	Point(int _x=0,int _y=0):x(_x),y(_y) {}
	Point operator - (const Point& b) const {
		return Point(b.x-x,b.y-y);
	}
	bool operator < (const Point& b) const {
		return x<b.x||(x==b.x&&y<b.y);
	}
} p[maxn];

typedef Point Vector;

double Dist(Point a,Point b) {
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int Cross(Vector a,Vector b) {
	return a.x*b.y-a.y*b.x;
}

int Andrew(int n,Point* p,Point* ans) {
	sort(p+1,p+n+1);
	int top=0;
	for(int i=1; i<=n; i++) {
		while(top>1&&Cross(ans[top-1]-ans[top],ans[top-1]-p[i])>=0)top--;
		ans[++top]=p[i];
	}
	int k=top;
	for(int i=n-1; i>=1; i--) {
		while(top>k&&Cross(ans[top-1]-ans[top],ans[top-1]-p[i])>=0)top--;
		ans[++top]=p[i];
	}
	if(n>1)top--;
	return top;
}

int t,n,k;

double Cal(int S) {
 	static Point tmp[maxn],ans[maxn];
	int cnt=0;
	for(int i=1; i<=n; i++)if(S&(1<<(i-1)))tmp[++cnt]=p[i];
	int tot=Andrew(cnt,tmp,ans);
	ans[tot+1]=ans[1];
	double Min=1e18;
	for(int i=1; i<=tot; i++) {
		double Max=0;
		for(int j=1; j<=tot; j++)Max=max(Max,fabs(Cross(ans[i]-ans[i+1],ans[i]-ans[j]))/Dist(ans[i],ans[i+1])/2);
		Min=min(Min,Max);
	}
	return Min;
}

double f[maxs][maxn];

int main() {
	t=Get_Int();
	while(t--) {
		n=Get_Int();
		k=Get_Int();
		for(int i=1; i<=n; i++) {
			p[i].x=Get_Int();
			p[i].y=Get_Int();
		}
		for(int S=1; S<(1<<n); S++)f[S][1]=Cal(S);
		for(int i=2; i<=k; i++)
			for(int S=1; S<(1<<n); S++) {
				f[S][i]=1e18;
				for(int T=S; T; T=(T-1)&S)f[S][i]=min(f[S][i],max(f[S^T][i-1],f[T][1]));
			}
		printf("%0.10lf\n",f[(1<<n)-1][k]);
	}
	return 0;
}