icpc2016SWERC-A

简要题意

平面上给定 \(n\) 个机械臂的长度和目标点，构造一个从坐标系原点出发的 \(n\) 个机械臂折线，使得折线另一端离目标点尽量近。\(n\le 20\) 坐标绝对值 \(2\times 10^4\) 。

题解

首先感觉这个机械臂很灵活，可以通过调整到达连续的点，那么考虑给你了一串机械臂，它能够到达哪些点，经过简单观察即可发现，可达点是一个圆或者一个圆环，形式化地，记机械臂长度数组为 \(a\) ，元素之和为 \(s\) ，最大值为 \(mx\) ，那么如果 \(mx\le s-mx\) 可达点就是一个半径为 \(r_2=s\) 的圆，如果 \(mx>s-mx\) 那么可达点就是一个内径 \(r_1=s-2mx\) 外径 \(r_2=s\) 的圆环。

我们发现我们总是可以通过调整使得机械臂末尾到达可达点区域内的任意一点，那么如果目标点在可达点外，就可以容易解决，如果在可达点内，就要通过调整使得机械臂终点最终在目标点处。

考虑如何调整，想到模拟退火，模拟当前这根机械臂 \(i\) 的角度，那么目标是使得目标点在 \(suf_{i+1}\) 这些机械臂的可达点内，那么考虑价值函数为当前角度所产生的 \(suf_{i+1}\) 的可达点区域与目标点的距离，就可以模拟退火了。但是经过进一步思考发现，价值函数的图像是单峰或者对称双峰的，那么我们只需要爬山即可完成调整，总复杂度为 \(O(Cn)\) 其中 \(C\) 为常数，由单次爬山的运行次数决定。

Beside：不要把 \(\text{getdis}\) 函数里的 \(\text{db}\) 写成 \(\text{int}\) 。除此之外，本题还有 \(O(n\log v)\) 的确定性算法。

代码

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(a) (int(a.size()))

typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef vector<int> vi;
#define debug(...) fprintf(stderr, __VA_ARGS__)
mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { uniform_int_distribution<ll> dist(l, r); return dist(gen); }

const db PI = acos(-1);

const int N = 30;
int n, l[N], sum[N], x, y, mx[N], r1[N], r2[N];
db getdis(pdd a, pdd b) {
    db x = a.fi - b.fi, y = a.se - b.se;
    return sqrt(x * x + y * y);
}
bool isIn(int x, pii seg) { return seg.fi <= x && x <= seg.se; }
db calc(pdd center, pdd R, pdd point) {
    db dis = getdis(center, point);
    // if(R.fi <= dis && dis <= R.se) return 0;
    if(fabs(fabs(dis - R.fi) + fabs(dis - R.se) - (R.se - R.fi)) < 1e-6) return 0;
    else return fmin(fabs(dis - R.fi), fabs(dis - R.se));
}
pdd operator+(pdd a, pdd b) { return Mp(a.fi + b.fi, a.se + b.se); }
pdd operator-(pdd a, pdd b) { return Mp(a.fi - b.fi, a.se - b.se); }
pdd mulAngle(int len, db angle) { return Mp(len * cos(angle), len * sin(angle)); }
db norm(db x) { return x > PI ? x - 2 * PI : x < -PI ? x + 2 * PI : x; }
db Rand() { return get(0, 1e9) / 1e9; }
signed main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &l[i]);
    for(int i = n; i; i--) {
        sum[i] = sum[i + 1] + l[i];
        mx[i] = max(mx[i + 1], l[i]);
        r1[i] = max(0, 2 * mx[i] - sum[i]);
        r2[i] = sum[i];
    }
    scanf("%d %d", &x, &y); pdd nw = Mp(0, 0);
    if(!isIn(getdis(Mp(0, 0), Mp(x, y)), Mp(r1[1], r2[1]))) {
        db angle = atan2(y, x), d = getdis(Mp(0, 0), Mp(x, y));
        if(abs(r1[1] - d) < abs(r2[1] - d)) {
            for(int i = 1; i <= n; i++) {
                if(l[i] != mx[1]) nw = nw - mulAngle(l[i], angle);
                else nw = nw + mulAngle(l[i], angle);
                printf("%.10lf %.10lf\n", nw.fi, nw.se);
            }
        } else {
            for(int i = 1; i <= n; i++) {
                nw = nw + mulAngle(l[i], angle);
                printf("%.10lf %.10lf\n", nw.fi, nw.se);
            }
        }
        return 0;
    }
#define getval(_) (calc(nw + mulAngle(l[i], _), Mp(r1[i + 1], r2[i + 1]), Mp(x, y)))
    for(int i = 1; i <= n; i++) {
        db angle = 0, best_angle = 0;
        while(fabs(getval(best_angle)) > 1e-6) {
            db T = 2 * PI;
            while(T > 1e-6) {
                db toangle = norm(angle + T * (Rand() * 2 - 1));
                db delta = getval(toangle) - getval(angle);
                if(delta < 0) angle = toangle;
                T *= 0.99;
                if(getval(angle) < getval(best_angle)) best_angle = angle;
            }
        }
        nw = nw + mulAngle(l[i], best_angle);
        printf("%.10lf %.10lf\n", nw.fi, nw.se);
    }
    debug("time=%.4lfs\n", (db)clock()/CLOCKS_PER_SEC);
    return 0;
}