自动搬运

查看原文

来自洛谷，原作者为

	Yukikaze_ **

搬运于2025-08-24 21:37:45，当前版本为作者最后更新于2020-05-23 00:04:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，根据题目意思，显然最短路径有一个性质：只在节点处转弯

于是我们考虑枚举每一对点，算出它们之间走直线的距离，然后跑最短路就可以了。

那么，该怎么求最短路呢？

最短路可以用 空地走过的总长度*u0+四边形内花费的总价值计算

对于凸四边形，一条线段（注意线段！！）和它至多有两个交点，所以我们直接找出线段和凸四边形的所有交点并去重，如果刚好剩下两个交点直接算距离和代价了，否则线段和多边形没有交点。

（注意：线段和四边形的交点如果是四边形两个相邻的顶点，也当做无交点处理）

对于凹四边形，可以找出它大于180度的角，并沿这个角的顶点所在的对角线将它分为两个三角形，接着就是和凸四边形一样的做法了。

（注意：被分开的三角形原本有一条边是在四边形内的，如果线段和三角形共这条边，不能当做无交点处理，共其它边则可以当做无交点处理）

处理完每一对距离，就可以直接跑最短路了，复杂度是 (4n)^3 的，我的代码由于stl用的太多，加上写的太丑，所以开O2才过的去。

考场代码改了改：

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define d(i,j) ((i-1)*4+j+3)
#define P pair<ld,int>
using namespace std;
typedef long double ld;
const ld eps=1e-4,inf=1e12;
const int N=415,M=200010;
int ppp=0;
ld dt[N],w[M],f[M],dis[N],g[N];
int n,s=1,t=2,siz[N],vis[N],fst[N],nxt[M],u[M],v[M],tot;//siz:单个图形中点的数量 
bool del[N],fl[N];//del:四边形被割开后被删掉（移走）的点，fl：被割开的那条边经过的点（对应注意2） 
priority_queue<P > q;
struct aa
{
	ld x,y;
	bool operator <(const aa &b)const{return fabs(x-b.x)<eps? y<b.y:x<b.x;}
	bool operator ==(const aa &b)const{return fabs(x-b.x)+fabs(y-b.y)<eps;}
	aa operator +(const aa &b)const{return aa{x+b.x,y+b.y};}
	aa operator -(const aa &b)const{return aa{x-b.x,y-b.y};}
	aa operator *(const ld &b)const{return aa{x*b,y*b};}
	ld operator *(const aa &b)const{return x*b.x+y*b.y;}
	ld operator ^(const aa &b)const{return x*b.y-y*b.x;}
	ld len() {return sqrt(x*x+y*y);}
	void read() {scanf("%Lf%Lf",&x,&y);}
}pt[N];
struct bb {aa s,t;};
void add(int lu,int lv,ld lw,ld lf)
{
	u[++tot]=lu,v[tot]=lv,w[tot]=lw,f[tot]=lf,nxt[tot]=fst[lu],fst[lu]=tot;
	u[++tot]=lv,v[tot]=lu,w[tot]=lw,f[tot]=lf,nxt[tot]=fst[lv],fst[lv]=tot;
}
bool px(bb a,bb b) {return fabs((b.t-b.s)^(a.t-a.s))<eps;} //判断平行 
aa crs(bb a,bb b) {return b.s+(b.t-b.s)*(((b.s-a.s)^(a.t-a.s))/((a.t-a.s)^(b.t-b.s)));} //求交点 
bool inn(bb a,aa b) {return fabs((b-a.s).len()+(b-a.t).len()-(a.t-a.s).len())<eps;} //判断是否在直线上 
ld work2(bb a,int b)
{
	int i,j,fll=0,lf=-1;
	aa lg;
	vector<aa> pp;
	for(i=0;i<siz[b];i++)
	{
		bb lx=bb{pt[d(b,i)],pt[d(b,(i+1)%siz[b])]};
		if(px(lx,a)) continue;
		aa lp=crs(lx,a);
		if(inn(lx,lp)&&inn(a,lp)) pp.push_back(lp);
	}
	sort(pp.begin(),pp.end());
	for(i=0;i<pp.size();i++)
	{
		if(i&&pp[i]==pp[i-1]) continue;
		for(j=0;j<siz[b];j++)
			if(pt[d(b,j)]==pp[i])
				if(lf==-1) lf=j;
				else if(abs(j-lf)!=2||siz[b]==3&&(!fl[d(b,j)]||!fl[d(b,lf)])) return 0;
		if(!fll) fll=1,lg=pp[i];
		else return (lg-pp[i]).len();
	}
	return 0;
}//求一条线段和四边形（三角形）的公共部分 
void work(int a,int b)
{
	int i,j;
	ld len=(pt[b]-pt[a]).len(),res=0;
	bb lp=bb{pt[a],pt[b]};
	for(i=1;i<=n;i++)
	{
		ld lx=work2(lp,i);
		res+=dt[i]*lx,len-=lx;
	}
	res+=dt[0]*len,add(a,b,res,(pt[b]-pt[a]).len());
}//加边 
void dj()
{
	int i,j;
	for(i=1;i<N;i++) dis[i]=inf,vis[i]=0;
	dis[s]=0,g[s]=0,q.push(P(0,s));
	while(!q.empty())
	{
		int lx=q.top().second;
		q.pop();
		if(vis[lx]) continue;
		vis[lx]=1;
		for(i=fst[lx];i;i=nxt[i])
			if(dis[v[i]]>dis[lx]+w[i]+eps) dis[v[i]]=dis[lx]+w[i],g[v[i]]=g[lx]+f[i],q.push(P(-dis[v[i]],v[i]));
	}
}//最短路 
int main()
{
	int i,j;
	ld res=0;
	pt[s].read(),pt[t].read(),scanf("%Lf%d",&dt[0],&n);
	for(i=n;i;i--)
	{
		siz[i]=4;
		scanf("%Lf",&dt[i]);
		for(j=0;j<4;j++) pt[d(i,j)].read();
		res+=((pt[d(i,2)]-pt[d(i,1)])^(pt[d(i,0)]-pt[d(i,1)]))/2+((pt[d(i,0)]-pt[d(i,3)])^(pt[d(i,2)]-pt[d(i,3)]))/2;
		for(j=0;j<4;j++)
		{
			bb lp=bb{pt[d(i,(j+3)%4)],pt[d(i,j)]},lq=bb{pt[d(i,j)],pt[d(i,(j+1)%4)]};
			if(((lp.t-lp.s)^(lq.t-lq.s))<0)//凹四边形 
			{
				n++,del[d(i,3)]=del[d(n,3)]=1,siz[n]=siz[i]=3,dt[n]=dt[i];
				fl[d(n,0)]=fl[d(n,2)]=1;
				pt[d(n,0)]=pt[d(i,j)],pt[d(n,1)]=pt[d(i,(j+1)%4)],pt[d(n,2)]=pt[d(i,(j+2)%4)];
				if(j==3) pt[d(i,0)]=pt[d(i,1)],pt[d(i,1)]=pt[d(i,2)],pt[d(i,2)]=pt[d(i,3)],fl[d(i,0)]=fl[d(i,2)]=1;
				if(j==0) pt[d(i,1)]=pt[d(i,2)],pt[d(i,2)]=pt[d(i,3)],fl[d(i,0)]=fl[d(i,1)]=1;
				if(j==1) pt[d(i,2)]=pt[d(i,3)],fl[d(i,1)]=fl[d(i,2)]=1;
				if(j==2) fl[d(i,2)]=fl[d(i,0)]=1;
				break; //凹四边形新建一个三角形，并将原来的图形也变成三角形 
			}
		}
	}
	for(i=1;i<=d(n,3);i++)
		for(j=i+1;j<=d(n,3);j++)
			if(!del[i]&&!del[j]) work(i,j);
	dj();
	printf("%.2Lf\n%.2Lf\n%.2Lf",res,g[t],dis[t]);
	return 0;
}