http://www.lydsy.com/JudgeOnline/problem.php?id=2433
http://221.192.240.123:8586/JudgeOnline/showproblem?problem_id=1668题目已经讲得很清楚了
首先可以发现一个性质：路径的转折点只能在矩形的顶点上。这个可以用任意三角形内一点到两顶点的距离<另一点到这两顶点的距离来证明。
于是这个明显是有阶段性的，也即只能从左到右。于是可以Dp，当然也可以spfa或Dijkstra等等。
算法关键在于如何求出任意两点间的距离。
朴素做法要O(n^3)，这明显是过不了的。
我们考虑从每个点开始走，发现每次阻挡视野的都是刚刚走过的矩形的边。于是我们可以维护一个视野，用每个访问过的点更新视野的up or low。
Postscript:记得加上等号……
View Code
#include <cstdio> #include <algorithm> #include <cmath> typedef long long ll; const int N = 2000 + 9; struct Point { int x,y; Point(const int _x = 0,const int _y = 0): x(_x),y(_y){} }p[N * 4],S,T; int n,pre[N],start; double dis[N*4],v; inline ll sqr(const int x){return 1ll*x*x;} inline double Dis(const Point x,const Point y) {return std::sqrt(sqr(y.x-x.x) + sqr(y.y-x.y));} inline ll cpr(const Point x,const Point y,const Point z) { const ll x1 = y.x - x.x, y1 = y.y - x.y; const ll x2 = z.x - x.x, y2 = z.y - x.y; return x1*y2 - x2*y1; } bool check(const int up,const int low,const Point x,const Point y) { if (up && cpr(x,p[up],y) > 0 || low && cpr(x,p[low],y) < 0) return false; return true; } double Dijkstra() { static bool ins[N*4]; for (start = 1; start <= n; ++start) if (p[start].x >= S.x) break; for (int i = start--; i <= n; ++i) dis[i] = 99999999.0; dis[start] = 0; p[start] = S; dis[4*N - 1] = 999999999.0; pre[start] = -1; while (1) { int k = 4*N - 1; for (int i = start; i <= n; ++i) if (!ins[i] && dis[k] > dis[i]) k = i; if (n == k) return dis[k]; ins[k] = 1; if (k == 7) k = 7; int up = 0,low = 0; double tmp; for (int i = k + 1; i <= n; ++i) { if (check(up,low,p[k],p[i])) if (!ins[i] && dis[i] > (tmp = dis[k] + Dis(p[k],p[i]))) dis[i] = tmp; if (((i-1)%4+1)&1 && (!up || cpr(p[k],p[up],p[i]) <= 0)) up = i; else if (!(((i-1)%4+1)&1) && (!low || cpr(p[k],p[low],p[i]) >= 0)) low = i; if (up && low && cpr(p[k],p[up],p[low]) > 0) break; } } } int main() { #ifndef ONLINE_JUDGE freopen("2433.in","r",stdin); freopen("2433.out","w",stdout); #endif scanf("%d",&n); for (int i = 1; i <= n; ++i) { scanf("%d%d%d%d",&p[i*4-2].x,&p[i*4-2].y,&p[i*4-1].x,&p[i*4-1].y); p[i*4-3] = Point(p[i*4-2].x,p[i*4-1].y); p[i*4] = Point(p[i*4-1].x,p[i*4-2].y); } scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y); n *= 4; if (S.x > T.x) std::swap(S,T); for (; n; --n) if (p[n].x <= T.x) break; p[++n] = T; scanf("%lf",&v); printf("%.10f\n",Dijkstra()/v); }
转载于:https://www.cnblogs.com/lazycal/p/3264063.html
相关资源：JAVA上百实例源码以及开源项目