记录编号	118839	评测结果	AA
题目名称	[NWERC2007]飞行安全	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.611 s
提交时间	2014-09-09 22:02:15	内存使用	3.87 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<iomanip>
using namespace std;
#define sqr(x) (x)*(x)
typedef long double LD;
const int SIZE=50,SIZER=1500;
const LD eps=1e-10;
const LD pi=acos(-1.0);
bool qua_solve(LD a,LD b,LD c,LD &x1,LD &x2){//解一元二次方程,两根x1,x2
	LD delta=b*b-4*a*c;
	if(delta<0) return false;
	x1=(-b-sqrt(delta))/(a*2);
	x2=(-b+sqrt(delta))/(a*2);
	return true;
}
void dua_solve(LD a1,LD b1,LD c1,LD a2,LD b2,LD c2,LD &x,LD &y){//解二元一次方程组,两未知数x,y
	x=(c2*b1-c1*b2)/(a1*b2-a2*b1);
	y=(c2*a1-c1*a2)/(b1*a2-b2*a1);
}
class POINT{
public:
	LD x,y;
	void print(void){cout<<"("<<x<<" "<<y<<")";}
};
void print(POINT p){cout<<"("<<p.x<<" "<<p.y<<")";}
POINT operator - (POINT a,POINT b){return (POINT){a.x-b.x,a.y-b.y};}
POINT operator + (POINT a,POINT b){return (POINT){a.x+b.x,a.y+b.y};}
POINT operator * (POINT a,LD t){return (POINT){a.x*t,a.y*t};}
POINT CC_rotate(POINT a){return (POINT){-a.y,a.x};}//逆时针旋转90度
POINT CW_rotate(POINT a){return (POINT){a.y,-a.x};}//顺时针旋转90度
LD distsqr(POINT a,POINT b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
LD dist(POINT a,POINT b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
LD crp(POINT a,POINT b){return a.x*b.y-b.x*a.y;}//叉积
void calc_pll(POINT a,POINT b,LD R,POINT &c,POINT &d){//求解矩形的另外两个顶点
	LD len=dist(a,b);
	c=CW_rotate(b-a)*(R/len)+a;
	d=CC_rotate(a-b)*(R/len)+b;
}
class CIRCLE{
public:
	POINT o;
	LD r;
};
class PARA{//参数方程
public:
	POINT p;
	LD a,b;
	//x=p.x+at,y=p.y+bt
	POINT calc(LD t){
		return (POINT){p.x+a*t,p.y+b*t};
	}
	void print(void){
		p.print();cout<<a<<" "<<b<<endl;
	}
};
PARA turn_para(POINT a,POINT b){//a,b写成参数方程
	PARA ans;
	ans.p=a;
	ans.a=b.x-a.x;
	ans.b=b.y-a.y;
	return ans;
}
int intersection(PARA s,CIRCLE t,LD &t1,LD &t2){//参数方程和圆求交点
	s.p=s.p-t.o;
	if(!qua_solve(sqr(s.a)+sqr(s.b),s.p.x*s.a*2+s.p.y*s.b*2,sqr(s.p.x)+sqr(s.p.y)-sqr(t.r),t1,t2)) return 0;
	int ans=0;
	if(0<t2&&t2<1) swap(t1,t2);
	if(0<t1&&t1<1) ans++;
	if(0<t2&&t2<1) ans++;
	return ans;
}
bool intersection(PARA s,PARA t,LD &ts,LD &tt){//两参数方程求交点
	dua_solve(s.a,-t.a,s.p.x-t.p.x,s.b,-t.b,s.p.y-t.p.y,ts,tt);
	return 0.0<ts&&ts<1.0&&0.0<tt&&tt<1.0;
}
class REGION{//区域(多边形,矩形,圆)
public:
	bool type;//0:circle 1:polygon
	CIRCLE c;
	int m;
	PARA border[SIZE];
	void make_intersection(PARA s,int id,vector<pair<LD,int> > &inter){
		LD t1,t2;
		if(type==0){
			int temp=intersection(s,c,t1,t2);
			if(temp>=1) inter.push_back(make_pair(t1,id));
			if(temp>=2)inter.push_back(make_pair(t2,id));
		}
		else{
			for(int i=1;i<=m;i++){
				if(intersection(s,border[i],t1,t2)){
					inter.push_back(make_pair(t1,id));
				}
			}
		}
	}
};
class CONTI{//大陆
public:
	int m;
	POINT V[SIZE];
	//必须保证V[m+1]=V[1]
	LD area(void){
		LD ans=0;
		for(int i=1;i<=m;i++) ans+=crp(V[i],V[i+1]);
		return ans/0.5;
	}
	void re_arrange(void){//按照逆时针方向重新排列
		if(area()<0){
			int i=1,j=m+1;
			while(i<j){
				swap(V[i],V[j]);
				i++,j--;
			}
		}
	}
	void make_region(LD);
};
int N,C;
PARA check;//用来测试处于哪些区域内
POINT KP[SIZE];//关键点
PARA route[SIZE];//航线
CONTI con[SIZE];//大陆
REGION R[SIZER];//区域
int Rtot;//区域个数
vector<pair<LD,int> > inter;//交点
void CONTI::make_region(LD r){//生成所有区域
	if(r<eps) return;
	for(int i=1;i<=m;i++){
		Rtot++;
		R[Rtot].type=0;
		R[Rtot].c=(CIRCLE){V[i],r};
	}
	for(int i=1;i<=m;i++){
		POINT a,b;
		calc_pll(V[i],V[i+1],r,a,b);
		Rtot++;
		R[Rtot].type=1;
		R[Rtot].m=4;
		R[Rtot].border[1]=turn_para(V[i],a);
		R[Rtot].border[2]=turn_para(a,b);
		R[Rtot].border[3]=turn_para(b,V[i+1]);
		R[Rtot].border[4]=turn_para(V[i+1],V[i]);
	}
}
void make_region(LD r){//生成所有区域
	Rtot=C;
	for(int i=1;i<=C;i++) con[i].make_region(r);
}
void make_intersection(PARA s){//生成s与区域的所有交点
	inter.clear();
	for(int i=1;i<=Rtot;i++) R[i].make_intersection(s,i,inter);
	sort(inter.begin(),inter.end());
}
bool inside[SIZER]={0};
bool test(LD R){//测试距离R
	make_region(R);
	make_intersection(check);//看起点在哪些区域
	memset(inside,0,sizeof(inside));
	for(int i=0;i<inter.size();i++) inside[inter[i].second]^=1;
	int tot=0;
	for(int i=1;i<=Rtot;i++) tot+=inside[i];
	for(int i=1;i<N;i++){//飞到下一个路径点,看中间是否脱离了"保护范围"
		make_intersection(route[i]);
		for(int j=0;j<inter.size();j++){
			if(inside[inter[j].second]) tot--;
			else tot++;
			inside[inter[j].second]^=1;
			if(j&&inter[j].first-inter[j-1].first<=eps||j<inter.size()-1&&inter[j+1].first-inter[j].first<=eps) continue;
			if(!tot) return false;//相邻很近的一进一出不算
		}
	}
	return true;
}
void init(void){
	scanf("%d%d",&C,&N);
	for(int i=1;i<=N;i++){
		cin>>KP[i].x>>KP[i].y;
		KP[i].x-=eps,KP[i].y+=eps;
	}
	for(int i=1;i<N;i++) route[i]=turn_para(KP[i],KP[i+1]);
	for(int i=1;i<=C;i++){
		scanf("%d",&con[i].m);
		for(int j=1;j<=con[i].m;j++) cin>>con[i].V[j].x>>con[i].V[j].y;
		con[i].V[con[i].m+1]=con[i].V[1];
		con[i].re_arrange();
		R[i].type=1;R[i].m=con[i].m;
		for(int j=1;j<=con[i].m;j++) R[i].border[j]=turn_para(con[i].V[j],con[i].V[j+1]);
	}
	check=turn_para(KP[1],(POINT){30000.0,30000.0});
}
void work(void){
	LD l=0.0,r=30000;
	int tot=0;
	while(++tot<=200){
		LD mid=(l+r)/2.0;
		if(test(mid)) r=mid;
		else l=mid;
	}
	cout<<setiosflags(ios::fixed)<<setprecision(6)<<(l+r)/2.0<<endl;
}

int main(){
	freopen("flightsafety.in","r",stdin);
	freopen("flightsafety.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		init();
		work();
	}
	return 0;
}