火焰之地传送门
凭心而论这题挺水的，一道计算几何加工的最短路。
用前面墙的个数*4+当前墙上的序号表示点的序号，对于每个点（包括起点和终点），枚举其后面墙上的所有点一一判断是否可与之相连，能相连就连边，最后跑一遍Floyd。
判断直接用数学公式做一次函数就行。
呆马：
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define maxn 25 using namespace std; int n; struct node { double x,gap[5]; }que[maxn]; double floyd[101][101]; bool pan(int a,int b,int h1,int h2) { if(b-a<2) return 1; double x1=que[a].x; double x2=que[b].x; double y1=que[a].gap[h1]; double y2=que[b].gap[h2]; double k=(y1-y2)/(x1-x2); double t=y1-x1*k; for(int i=a+1;i<b;i++) { double now=que[i].x*k+t; if(now<que[i].gap[1]||now>que[i].gap[2]&&now<que[i].gap[3]||now>que[i].gap[4]) return 0; } return 1; } void add(int a,int b,int h1,int h2) { if(!pan(a,b,h1,h2)) return; double x1=que[a].x; double x2=que[b].x; double y1=que[a].gap[h1]; double y2=que[b].gap[h2]; floyd[a*4+h1][b*4+h2]=floyd[b*4+h2][a*4+h1]=sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)); } int main() { scanf("%d",&n); memset(floyd,127,sizeof(floyd)); for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf%lf",&que[i].x,&que[i].gap[1],&que[i].gap[2],&que[i].gap[3],&que[i].gap[4]); que[0].x=0;que[++n].x=10; for(int i=1;i<=4;i++) que[0].gap[i]=que[n].gap[i]=5; for(int i=0;i<n;i++) for(int j=i+1;j<=n;j++) for(int a=1;a<=4;a++) for(int b=1;b<=4;b++) add(i,j,a,b); for(int i=0;i<101;i++) floyd[i][i]=0; for(int k=1;k<=n*4+4;k++) for(int i=1;i<=n*4+4;i++) for(int j=1;j<=n*4+4;j++) floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j]); printf("%.2lf",floyd[1][n*4+1]); return 0; }
转载于:https://www.cnblogs.com/charlesss/p/10720264.html
