• https://www.luogu.com.cn/problem/P1995

先复习一下 这个题。。。

#include <lastweapon/geometry>
using namespace lastweapon;
using namespace CG;

const int N = 21;

DB dp[N][4], x[N], y[N][4];
int n;

bool ok(int i0, int j0, int i1, int j1) {
    Line s(Po(x[i0], y[i0][j0]), Po(x[i1], y[i1][j1]));
    FOR(i, i0+1, i1) {
        if(Seg(Po(x[i], y[i][0]), Po(x[i], y[i][1])).sgn(s) < 0 &&
           Seg(Po(x[i], y[i][2]), Po(x[i], y[i][3])).sgn(s) < 0) return 0;
    }
    return 1;
}

int main() {

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); REP(j, 4) y[0][j] = 5;
    REP_1(i, n) {
        RF(x[i]); REP(j, 4) RF(y[i][j]);
    }
    x[++n] = 10; REP(j, 4) y[n][j] = 5;
    REP_1(i, n) REP(j, 4) dp[i][j] = OO;

    FOR(i, 0, n) REP(j, 4) FOR_1(ii, i+1, n) REP(jj, 4) {
        if (ok(i, j, ii, jj)) checkMin(dp[ii][jj], dp[i][j] + dist(Po(x[i], y[i][j]), Po(x[ii], y[ii][jj])));
    }

    printf("%.2f\n", dp[n][0]);
}

然后可以先直接输出 dist(s, t) 怒骗 20 分。。。（因为你数据里肯定也必须有这种类型的数据吧。。。）

#include <lastweapon/geometry>
using namespace lastweapon;
using namespace CG;

const int N = int(2e3) + 9;

struct Rect {
    int x0, y0, x1, y1;
    void in() {
        RD(x0, y0, x1, y1);
    }
} R[N];
DB f[N][2]; Po s, t;
int n;

DB gao() {
    return dist(s, t);
}

int main() {

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); REP(i, n) R[i].in(); s.in(); t.in();
    printf("%9f\n", gao() / RF());
}

核心的区别就是 vijos 那个题，我可以 O(n3) dp，暴力 check 两点之间的可达性。.而 NOI 这个题，每次只有一段空隙，所以可通过区域是一个不断缩小的扇形。。于是复杂度就 O(n2) 了。

顺便原版 vijos 的那个版本，其实我们也可以用平衡木来维护可通过的区域。。。
回到实现。。孤立的 s 点和 t 点很烦。。而且有很多 corner case。。

我们想办法把 s 和 t 都视为一个退化的矩形。。。。这样我就不用写额外的代码了。

#include <lastweapon/geometry>
using namespace lastweapon;
using namespace CG;

const int N = int(2e3) + 9;

struct Rect {
    int x0, y0, x1, y1;
    void in() {
        RD(x0, y0, x1, y1);
    }
} R[N];
DB f[N][2]; int l[N], r[N]; Po s, t;

int n;

bool cmp(const Rect R, int x) {
    return R.x1 < x;
}

DB gao() {

    int si = lower_bound(R+1, R+n+1, s.x, cmp) - R;
    int ti = lower_bound(R+1, R+n+1, t.x, cmp) - R;
    if (si > ti) swap(si, ti), swap(s, t);

    if (R[si].x1 != s.x) --si;
    ++ti; if (R[ti].x0 == t.x) ++ti;

    R[si].x1 = s.x; R[si].y0 = R[si].y1 = s.y;
    R[ti-1].x1 = t.x; R[ti].x0 = t.x; R[ti].y0 = R[ti].y1 = t.y;
    FOR(i, si+1, ti) f[i][0] = f[i][1] = OO; f[si][0] = f[si][1] = 0;
    FOR(i, si, ti) l[i] = max(R[i].y0, R[i+1].y0), r[i] = min(R[i].y1, R[i+1].y1);
    --ti;

#define u f[i][j]
#define v f[ii][jj]
#define w dist(pu, pv)

    FOR(i, si, ti) REP(j, 2) {
        Po pu(R[i].x1, j ? r[i] : l[i]);
        DB ar = PI/2, al = -ar;

        //cout << pu << ": " << u << endl;

        FOR_1(ii, i+1, ti) REP(jj, 2) {
            Po pv(R[ii].x1, jj ? r[ii] : l[ii]);
            DB t = atan2(pv.y-pu.y, pv.x-pu.x); if (t > PI) t -= 2*PI;
            if (al <= t && t <= ar) checkMin(v, u + w);
            if (jj) checkMin(ar, t); else checkMax(al, t);
        }
    }
    return f[ti][0];
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); REP_1(i, n) R[i].in(); s.in(); t.in();
    printf("%9f\n", gao() / RF());
}

Posted by xiaodao
Category: 日常