[NOI2011]智能车比赛 (计算几何 DAG)

/*
可以发现, 最优路径上的所有拐点, 基本上都满足一定的性质, 也就是说是在矩形上的拐角处
所以我们可以把他们提出来, 单独判断即可 由于我们提出来的不超过2n + 2个点, 我们将其按照x坐标排序, 这样就只能单方向走
n^2枚举判断两个点之间能不能直接走, 然后连边DAGdp即可 */ #include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<iostream>
#define ll long long
#define M 4080
#define mmp make_pair
using namespace std;
const double inf = pow(2, 60);
int read() {
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
struct Note {
int x, y, f;
bool operator < (const Note &b) const {
return x == b.x ? y < b.y : x < b.x;
}
} note[M];
int n, m, L, R, lx[M], ly[M], rx[M], ry[M], bex, bey, edx, edy, tp;
vector<pair<int, double> > to[M];
double f[M], v, ans;
double dis(Note a, Note b) {
return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}
int main() {
n = read();
for(int i = 1; i <= n; i++) lx[i] = read(), ly[i] = read(), rx[i] = read(), ry[i] = read();
bex = read(), bey = read(), edx = read(), edy = read();
if(bex == edx) {
ans = (bey > edy) ? bey - edy : edy - bey;
} else {
if(bex > edx) swap(bex, edx), swap(bey, edy);
note[++tp] = (Note) {
bex, bey, 1
};
note[++tp] = (Note) {
edx, edy, 2
};
for(int i = 1; i < n; i++) {
int maxx = max(ly[i], ly[i + 1]), minn = min(ry[i], ry[i + 1]);
note[++tp] = (Note) {
lx[i + 1], minn, 3
};
note[++tp] = (Note) {
lx[i + 1], maxx, 4
};
}
sort(note + 1, note + tp + 1);
for(int i = 1; i <= tp; i++) {
if(note[i].f == 1) L = i;
if(note[i].f == 2) R = i;
}
for(int i = L; i <= R; i++) {
double le = -inf, re = inf;
for(int j = i + 1; j <= R; j++) {
if(note[j].x == note[i].x) {
to[j].push_back(mmp(i, note[j].y - note[i].y));
continue;
}
double slp = 1.0 * (note[j].y - note[i].y) / (note[j].x - note[i].x);
if(slp >= le && slp <= re) to[j].push_back(mmp(i, dis(note[i], note[j])));
if(note[j].f == 4) le = max(le, slp);
else re = min(re, slp);
}
}
for(int i = L + 1; i <= R; i++) {
f[i] = inf;
for(int j = 0; j < to[i].size(); j++) {
// cout << to[i][j].second << "\n";
f[i] = min(f[i], f[to[i][j].first] + to[i][j].second);
}
}
ans = f[R];
}
cin >> v;
ans /= v;
printf("%.8lf\n", ans);
return 0;
}
上一篇:freeCAD特性列表


下一篇:CentOS7 + mono +Jexus 环境的搭建