cf 1252 I 路径规划

貌似是比较防AK的几何模板题。LRJ书上的提到运动规划模型是它的简化版，思路也可以参考。

题意：平面上给定 n (n<=50) 个大小不同的圆，要求给出一条从起点到终点的折线路径，使路径与圆不相交，且不超出给定区域。坐标范围均在0~1000内。

比较容易想到只要在所有可能的切线上走一定能走到终点。题目也刚好规定与圆相切不算相交，证实了整个想法。然后就是套模板生成所有切线，共生成O(n^2)条。注意如果切线被割断，则丢弃。然后延长切线至尽可能长，顶到边界或其他圆。然后从起点bfs一遍就可以了，bfs时暴力枚举所有线段，判断是否有交即可。最后答案对路径上的线算一遍交点。
这里共线的情况也不必考虑，直接视为不相交。
如果这题圆与边界相交，还要注意圆把边界割为几段的情况。

```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
typedef long double db;
```
```
 
```
```
const db eps=1e-7,PI=acos(-1);
```
```
 
```
```
bool eq(db x){return fabs(x)<eps;}
```
```
int sgn(db x){
```
```
	if (x<-eps) return -1;
```
```
	return x>eps;
```
```
}
```
```
 
```
```
#define Vec const vec&
```
```
#define Point const point&
```
```
struct vec{
```
```
	db x,y;
```

	vec(db theta){x=cosl(theta),y=sinl(theta);}

```
	vec(db x, db y):x(x),y(y){}
```
```
	vec(){}
```

	vec operator+(Vec v)const{return {x+v.x,y+v.y};}

	vec operator-(Vec v)const{return {x-v.x,y-v.y};}

	vec operator*(db a)const{return {x*a,y*a};}

	vec operator/(db a)const{return {x/a,y/a};}

	db operator|(Vec v)const{return x*v.x+y*v.y;}

	db operator&(Vec v)const{return x*v.y-y*v.x;}

	db operator!()const{return sqrt(x*x+y*y);}

	bool operator==(Vec v)const{return eq(x-v.x) && eq(y-v.y);}

```
	vec l90()const{return {-y,x};}
```
```
	db ang()const{return atan2l(y,x);}
```

	void rd(){double tx,ty;scanf("%lf%lf",&tx,&ty); x=tx,y=ty;}

	void prt(){printf("(%f,%f)",(double)x,(double)y);}

```
};
```
```
typedef vec point;
```
```
 
```

vec lineInt(Vec p, Vec vp, Vec q, Vec vq){

```
	db t=(vq & p-q)/(vp&vq);
```
```
	return p+vp*t;
```
```
}
```
```
db lineDis(Point p, Point s, Vec v){
```
```
	return fabs(v & p-s)/!v;
```
```
}
```

bool rectCover(Point a1, Point a2, Point b1, Point b2){return

```
	min(a1.x,a2.x)<=max(b1.x,b2.x)+eps &&
```
```
	min(b1.x,b2.x)<=max(a1.x,a2.x)+eps &&
```
```
	min(a1.y,a2.y)<=max(b1.y,b2.y)+eps &&
```
```
	min(b1.y,b2.y)<=max(a1.y,a2.y)+eps;
```
```
}
```
```
//test if segment A1-A2 B1-B2 is cross
```

int segCross(Point a1, Point a2, Point b1, Point b2){

	if (!rectCover(a1,a2,b1,b2)) return 0; //not necessary

	db c1=sgn(a2-a1&b1-a1), c2=sgn(a2-a1&b2-a1);

	db c3=sgn(b2-b1&a1-b1), c4=sgn(b2-b1&a2-b1);

```
	if (c1*c2>0 || c3*c4>0) //no cross
```
```
		return 0; 
```

	if (c1==0 && c2==0||c3==0 && c4==0) //segment on same line

```
		return 0; 
```

	if (c1*c2<0 && c3*c4<0) return 1; //normal cross

```
	return 2; //a point on line
```
```
}
```
```
 
```
```
#define Circle const circle &
```
```
struct circle{
```
```
	vec c; db r;
```

	vec angle(db theta)const{return c+vec(theta)*r;}

```
}cir[51];
```
```
 
```
```
int cirTang(vec p, Circle c, vec *ans){
```
```
	db d=!(c.c-p);
```
```
	//if (sgn(d-c.r)<=0) return 0;
```
```
	if (eq(d-c.r)){
```
```
		ans[0]=p;
```
```
		return 1;
```
```
	}
```
```
	db base=(p-c.c).ang();
```
```
	db ang=acos(c.r/d);
```
```
	ans[0]=c.angle(base-ang);
```
```
	ans[1]=c.angle(base+ang);
```
```
	return 2;
```
```
}
```
```
 
```

int cirTang(circle A, circle B, point *a, point *b){

```
	int cnt=0;
```

	//if (A.c==B.c && eq(A.r-B.r)) return -1;

```
	if (A.r<B.r) swap(A,B),swap(a,b);
```
```
	db d=!(A.c-B.c);
```
```
	db diff=A.r-B.r, sum=A.r+B.r;
```
```
	//if (sgn(d-diff)<0) return 0;
```
```
	db base=(B.c-A.c).ang();
```
```
	//if (eq(d-diff)){
```
```
	//	a[0]=A.angle(base);
```
```
	//	b[0]=a[0];
```
```
	//	return 1;
```
```
	//}
```
```
	db ang=acos((A.r-B.r)/d);
```

	a[cnt]=A.angle(base+ang); b[cnt++]=B.angle(base+ang);

	a[cnt]=A.angle(base-ang); b[cnt++]=B.angle(base-ang);

```
	ang=acos((A.r+B.r)/d);
```

	a[cnt]=A.angle(base+ang); b[cnt++]=B.angle(PI+base+ang);

	a[cnt]=A.angle(base-ang); b[cnt++]=B.angle(PI+base-ang);

```
	return 4;
```
```
}
```
```
 
```

int segInt(Vec a, Vec b, Circle c, pair<db,db> &ans){

```
	vec v=b-a, u=a-c.c;
```
```
	db e=v|v,f=v|u*2,g=(u|u)-c.r*c.r;
```
```
	db delta=f*f-4*e*g;
```

	if (sgn(c.r-lineDis(c.c,a,b-a))<=0) return 0;

```
	db t1=(-f-sqrt(delta))/(2*e);
```
```
	db t2=(-f+sqrt(delta))/(2*e);
```
```
	ans={t1,t2};
```
```
	return 2;
```
```
}
```

int lineInt(Vec a, Vec b, Circle c, point *ans){

```
	vec v=b-a, u=a-c.c;
```
```
	db e=v|v,f=v|u*2,g=(u|u)-c.r*c.r;
```
```
	db delta=f*f-4*e*g;
```

	if (sgn(c.r-lineDis(c.c,a,b-a))<=0) return 0;

```
	db t1=(-f-sqrt(delta))/(2*e);
```
```
	db t2=(-f+sqrt(delta))/(2*e);
```
```
	vec a1=a+v*t1, a2=a+v*t2;
```
```
	int cnt=0;
```
```
	ans[cnt++]=a1; ans[cnt++]=a2;
```
```
	return 2;
```
```
}
```
```
 
```
```
struct line{
```
```
	vec p1,p2;
```
```
}li[50010];
```
```
int n;
```

vec tmp[4],tmp2[4],__[4]; line bod[4];vec kp[4];

```
bool inbod(Vec p){
```

	return p.x>=kp[2].x-eps && p.x<=kp[3].x+eps && p.y>=kp[2].y-eps && p.y<=kp[3].y+eps;

```
}
```
```
 
```
```
bool expli(vec &p1, vec &p2){
```
```
	db l=-1e20,r=1e20;
```

	if (!inbod(p1) || !inbod(p2)) return 0;

```
	for (int i=0;i<n;i++){
```
```
		pair<db,db> t;
```

		if (segInt(p1,p2,cir[i],t)==0) continue;

		if (t.second>eps && t.second<1-eps || t.first>eps && t.first<1-eps) return 0;

```
		if (t.first>0.5) r=min(r,t.first);
```
```
		else l=max(l,t.second);
```
```
	}
```
```
	for (int i=0;i<4;i++){
```
```
		vec vp=p2-p1, vq=bod[i].p2-bod[i].p1;
```
```
		if (!eq(vp&vq)){
```
```
			db t=(vq & p1-bod[i].p1)/(vp&vq);
```
```
			if (t>0.5) r=min(r,t);
```
```
			else l=max(l,t);
```
```
		}
```
```
	}
```
```
	vec vp=p2-p1;
```
```
	p2=p1+vp*r;
```
```
	p1=p1+vp*l;
```
```
	return 1;
```
```
}
```
```
 
```
```
 
```
```
vec lineInt(line l1, line l2){
```

	return lineInt(l1.p1,l1.p2-l1.p1,l2.p1,l2.p2-l2.p1);

```
}
```
```
 
```
```
int qu[50010],pre[50010],qh,qt,lic;
```
```
bool vis[50010];
```
```
set<int> lend;
```
```
double ttr;
```
```
int main(){
```
```
	cin>>n; 
```
```
	for (int i=0;i<4;i++) kp[i].rd();
```
```
	swap(kp[0],kp[2]);swap(kp[3],kp[1]);
```

	bod[0]={{kp[2].x,kp[2].y},{kp[3].x,kp[2].y}};

	bod[1]={{kp[2].x,kp[3].y},{kp[3].x,kp[3].y}};

	bod[2]={{kp[2].x,kp[2].y},{kp[2].x,kp[3].y}};

	bod[3]={{kp[3].x,kp[2].y},{kp[3].x,kp[3].y}};

```
	for (int i=0;i<n;i++)
```

		cir[i].c.rd(),scanf("%lf",&ttr),cir[i].r=ttr;

```
	tmp[0]=kp[0],tmp[1]=kp[1];
```

	if (expli(tmp[0],tmp[1])) return puts("0"),0;

```
	for (int i=0;i<n;i++){
```
```
		for (int j=i+1;j<n;j++){
```
```
			cirTang(cir[i],cir[j],tmp,tmp2);
```
```
			for (int k=0;k<4;k++){
```

				if (expli(tmp[k],tmp2[k])) li[lic++]={tmp[k],tmp2[k]};

```
			}
```
```
		}
```
```
	}
```
```
	for (int i=0;i<2;i++)
```
```
		for (int j=0;j<n;j++){
```
```
			cirTang(kp[i],cir[j],tmp);
```
```
			for (int k=0;k<2;k++){
```
```
				vec tkp=kp[i];
```

				if (tmp[0]==tkp) tmp[0]=tkp+(tkp-cir[i].c).l90();

```
				if (expli(tmp[k],tkp)){
```

					if (i==0) pre[qt]=-1,qu[qt++]=lic,vis[lic]=1;

```
					else lend.insert(lic);
```
```
					li[lic++]={tmp[k],tkp};
```
```
				}
```
```
			}
```
```
		}
```

	sort(cir,cir+n,[](Circle a, Circle b){return a.c.x<b.c.x;});

```
	db cur=kp[2].x;
```
```
	line bo=bod[0];
```
```
	for (int i=0;i<n;i++){
```
```
		if (lineInt(bo.p1,bo.p2,cir[i],tmp))
```

			li[lic++]={{cur,kp[2].y},{tmp[0].x,kp[2].y}},

```
			cur=tmp[1].x;
```
```
	}
```

	li[lic++]={{cur,kp[2].y},{kp[3].x,kp[2].y}};

```
 
```
```
	cur=kp[2].x;
```
```
	bo=bod[1];
```
```
	for (int i=0;i<n;i++){
```
```
		if (lineInt(bo.p1,bo.p2,cir[i],tmp))
```

			li[lic++]={{cur,kp[3].y},{tmp[0].x,kp[3].y}},

```
			cur=tmp[1].x;
```
```
	}
```

	li[lic++]={{cur,kp[3].y},{kp[3].x,kp[3].y}};

```
 
```

	sort(cir,cir+n,[](Circle a, Circle b){return a.c.y<b.c.y;});

```
	cur=kp[2].y;
```
```
	bo=bod[2];
```
```
	for (int i=0;i<n;i++){
```
```
		if (lineInt(bo.p1,bo.p2,cir[i],tmp))
```

			li[lic++]={{kp[2].x,cur},{kp[2].x,tmp[0].y}},

```
			cur=tmp[1].y;
```
```
	}
```

	li[lic++]={{kp[2].x,cur},{kp[2].x,kp[3].y}};

```
 
```
```
	cur=kp[2].y;
```
```
	bo=bod[3];
```
```
	for (int i=0;i<n;i++){
```
```
		if (lineInt(bo.p1,bo.p2,cir[i],tmp))
```

			li[lic++]={{kp[3].x,cur},{kp[3].x,tmp[0].y}},

```
			cur=tmp[1].y;
```
```
	}
```

	li[lic++]={{kp[3].x,cur},{kp[3].x,kp[3].y}};

//	for (int i=0;i<qt;i++) cout<<qu[i]<<' ';cout<<'\n';

//	for (auto i:lend) cout<<i<<' ';cout<<'\n';

//	for (int i=0;i<lic;i++){cout<<i<<' '; li[i].p1.prt(); putchar(' '); li[i].p2.prt(); cout<<'\n';}

```
	while (qh<qt){
```
```
		int u=qu[qh];
```
```
		if (lend.count(u)){
```
```
			vector<vec> ans;
```
```
			int su=qh;
```
```
			while (~pre[su])
```

				ans.push_back(lineInt(li[qu[su]],li[qu[pre[su]]]))

```
//				,cout<<qu[su]<<' '
```
```
				,su=pre[su];
```

//			cout<<'\n'<<lineDis(cir[0].c,ans[0],kp[1]-ans[0])<<'\n';

```
			cout<<ans.size()<<'\n';
```
```
			for (int i=0;i<ans.size();i++)
```
```
				for (int j=i+1;j<ans.size();j++)
```
```
					assert(!(ans[i]==ans[j]));
```
```
			reverse(begin(ans),end(ans));
```
```
			for (auto it:ans)
```

				printf("%.15f %.15f\n",(double)it.x,(double)it.y);

```
			return 0;
```
```
		}
```

		for (int i=0;i<lic;i++) if (!vis[i] && segCross(li[u].p1,li[u].p2,li[i].p1,li[i].p2)){

```
			pre[qt]=qh;
```
```
			qu[qt++]=i;
```
```
			vis[i]=1;
```
```
		}
```
```
		qh++;
```
```
	}
```
```
 
```
```
	return 0;
```
```
}
```

fffasttime

cf 1252 I 路径规划

发表评论取消回复

发表评论 取消回复

发表评论取消回复