题解 『JROI-2』Dancing Line

JROI 的比赛题。
不是特别难想,但是一些关于浮点数的操作需要注意。
因为精度问题等浮点数的问题,赛场上 \(100 \to 4\),赛后也调了一晚上,交了一页多才过。

从一个点出发,每次只能顺时针或逆时针转 \(90\deg\),且相邻两次不能转的方向相同,乱序给出所有转折点,求所有线段的长度的平方除以 \(v^2\) 的和。

开始想着计算几何,没有什么想法,后来发现这题似乎还是解析几何好使!

观察样例的图片容易发现,对于除了头尾的另外一个点,经过它且垂直的线段只有一对。
而所有线段可以分成互相平行的两组,直到了这两组的斜率之后就可以把它们分别拿出来处理了。

然后就是解析几何令人头疼的问题了,精度,以及 \(0\) 斜率。赛场上因为把 eps 调得太精确了导致后面一堆 WA,把 eps 改成 1e-3 立刻过了大部分的点,还有一些点怎么调也过不去。

这就涉及到实现的精度问题了,我开始是算出和 x 轴夹角,再要用斜率的时候用 \(\tan\) 进行转换,这样的精度损失非常大,但转 \(90\deg\) 的时候只要给一个值加上 \(\frac{\pi}{2} \text{rad}\) 就可以了。
但是别忘了初中解析几何知识啊,不需要费这个力气,直接记录斜率,转 \(90\deg\) 就是用 \(-1\) 除就可以了。
尽量避免多次三角函数这样的复杂运算可以增加精度。

然后说说怎么处理 \(0\) 的问题。
若要除以 \(0\),可以把结果设置成一个常量 NaN,让 NaN > 1/eps,这样除以 \(0\) 就变成 NaN,而除以 NaN 又变回了 \(0\),刚好满足我们对斜率运算的要求。

注意

若除数小于 eps,除出来的会大于 NaN,所以除法结果大于 NaN 的也要看作 NaN。我因为这个调了很久。

最后在这道题中,分开所有斜率相同的线段时要用到与 \(x\) 轴的交点,若整个都竖起来了那根本没有交点,我们可以返回横坐标值以区别这些点,为了保险的话也可以乘一个随机值,防止被 hack(不过洛谷又没有 hack)。

偶尔做做这种浮点数题练习下浮点数操作也好。

代码
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <utility>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#define double long double
#define int long long
#define se second
#define fi first
const int N = 1000005, P = 998244353;
const double eps = 1e-3, Pi = acos(-1), NaN = 2021;
int n, v, ans, inv, tot;
double sl1, sl2;
std::vector<double> t;
bool flag;
struct twt { int x, y; } a[N];
std::pair<double, int> s[N];
int dis2(twt A, twt B) { return (B.x-A.x)*(B.x-A.x) + (B.y-A.y)*(B.y-A.y); }
int Pow(int a, int b) {
    int an = 1;
    for ( ; b; b >>= 1, a = a * a % P) 
        if (b & 1) an = an * a % P;
    return an;
}
double getS(twt A, twt B) {
    if (A.y < B.y) std::swap(A, B);
    int fm = A.x - B.x, fz = A.y - B.y;
    if (fm == 0) return NaN;
    else return (double)fz/fm;
}
double getb(twt A, double deg) {
    if (NaN-deg < eps) return A.x;
    double k = deg;
    return A.y - k * A.x;
}
signed main() {    
    srand(time(0));
    std::cin >> n >> v;
    n ++;
    inv = Pow(v*v%P, P-2);
    for (int i = 1; i <= n; i++) std::cin >> a[i].x >> a[i].y;
    
    while (!flag) {
        int tmp = rand()%n+1;
        std::swap(a[1], a[tmp]);
        t.clear();
        for (int i = 2; i <= n; i++) t.push_back(getS(a[1], a[i]));
        std::sort(t.begin(), t.end());
        for (int i = 0; i < (int)t.size(); i++) {
            double tmp = ((t[i] != 0) ? (-1/t[i]) : NaN);
            int p = std::lower_bound(t.begin(), t.end(), tmp) - t.begin();
            if (fabs(t[p] - tmp) < eps || (t[p]-NaN > eps && tmp-NaN > eps)) {
                sl1 = t[p], sl2 = t[i];
                flag = 1;
                break;
            }
        }
    }
    
    for (int i = 1; i <= n; i++) 
        s[++tot] = std::make_pair(getb(a[i], sl1), i);
    std::sort(s+1, s+tot+1);
    int st = 1;
    while (st < n && fabs(s[st].fi-s[st+1].fi) > eps) st ++;
    for (int i = st; i <= n && fabs(s[i].fi-s[i+1].fi) < eps; i += 2) 
        ans = (ans + dis2(a[s[i].se], a[s[i+1].se]) % P * inv % P) % P;
        
    tot = 0;
    for (int i = 1; i <= n; i++) 
        s[++tot] = std::make_pair(getb(a[i], sl2), i);
    std::sort(s+1, s+tot+1);
    st = 1;
    while (st < n && fabs(s[st].fi-s[st+1].fi) > eps) st ++;
    for (int i = st; i <= n && fabs(s[i].fi-s[i+1].fi) < eps; i += 2) 
        ans = (ans + dis2(a[s[i].se], a[s[i+1].se]) % P * inv % P) % P;
    std::cout << ans;
}

最后这题好像有个更简单的做法,按照横纵坐标排两次序就一定有一个是按照顺序的了。
这个做法简单得多也不用担心精度问题(

上一篇:补充


下一篇:Asymptote 自己搭建简易IDE