社区讨论

求助,开O2就过了,不开O2会Wa(估计是精度原因)

P5467[PKUSC2018] PKUSC参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo8os27j
此快照首次捕获于
2023/10/27 22:06
2 年前
此快照最后确认于
2023/10/27 22:06
2 年前
查看原帖
CPP
/*
        |\+++/|
    \  | ^  ^  \
   -- | #    # \
   \_|         \
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <iomanip>

const int N = 1550;
const double eps = 1e-7, pi = acos(-1);
int n, m;

int sign(double x) {
    if (x > eps) return 1;
    else if (x < -eps) return -1;
    else return 0;
}

int cmp(double a, double b) {
    return sign(a - b);
}

struct Vector {
    double x, y, theta;

    Vector () {}

    Vector(double _x, double _y) {
        x = _x, y = _y;
    }

    double len() {
        return sqrt(x * x + y * y);
    }

    bool operator < (Vector a) {
        return cmp(theta, a.theta) < 0;
    }

    friend bool operator == (Vector a, Vector b) {
        return cmp(a.x, b.x) == 0 && cmp(a.y, b.y) == 0;
    }

    Vector operator + (Vector a) {
        return Vector(x + a.x, y + a.y);
    }

    Vector operator - (Vector a) {
        return Vector(x - a.x, y - a.y);
    }

    Vector operator * (double a) {
        return Vector(x * a, y * a);
    }

    Vector operator / (double a) {
        return Vector(x / a, y / a);
    }

    double operator * (Vector a) {
        return x * a.y - y * a.x;
    }
}p[N];

struct Line {
    Vector u, v;

    Line () {}

    Line (Vector _u, Vector _v) {
        u = _u, v = _v;
    }

    double len() {
        return (v - u).len();
    }
}l[N];

double cnt = 0;

bool neline(Vector a, Line b) {
    // cnt += a.x + a.y + b.u.x + b.v.x + b.u.y + b.v.y;
    if (cmp(a.x, std::min(b.u.x, b.v.x)) == -1) return 0;
    if (cmp(a.x, std::max(b.u.x, b.v.x)) == 1) return 0;
    if (cmp(a.y, std::min(b.u.y, b.v.y)) == -1) return 0;
    if (cmp(a.y, std::max(b.u.y, b.v.y)) == 1) return 0;
    return 1;
}

bool online(Vector a, Line b) {
    // cnt -= a.x + a.y + b.u.x + b.v.x + b.u.y + b.v.y;
    return (neline(a, b) && (sign((a - b.u) * (a - b.v)) == 0));
}

Vector inter (Line a, Line b) {
    Vector w = a.u - b.u;
    double t = ((b.v - b.u) * w) / ((a.v - a.u) * (b.v - b.u));
    return a.u + (a.v - a.u) * t;
}

double dis(Vector a, Line b) {
    return fabs((b.u - a) * (b.v - a)) / b.len();
}

bool in(Vector x) {
    for (int i = 1; i <= m; ++i) {
        if (online(x, l[i])) return 0;
    }
    Line L = Line(x, x + Vector(0.2333, 0.6666));
    int cnt = 0;
    for (int i = 1; i <= m; ++i) {
        Vector y = inter(L, l[i]);
        if (sign(y.y - x.y) > 0 && neline(y, l[i])) cnt ^= 1;
    }
    return cnt;
}

double get(Vector a, Vector b, double r) {
    double res = 0;
    Vector c = (b - a) / (b - a).len();
    c = Vector(c.y, -c.x) * r;
    if (in(c)) {
        if (a.theta > b.theta) res += 2 * pi;
        res += b.theta - a.theta;
    }
    return res;
}

double solve(double r) {
    double ans = 0;
    if (sign(r) == 0) {
        if (in(Vector(0, 0))) ans += pi * 2;
        return ans;
    }
    std::vector<Vector> t;
    for (int i = 1; i <= m; ++i) {
        if (cmp(dis(Vector(0, 0), l[i]), r) >= 0) {
            continue;
        }
        Vector c = (l[i].v - l[i].u) / (l[i].v - l[i].u).len();
        Line Tl = (Line){Vector(0, 0), Vector(-c.y, c.x)};
        Vector T = inter(Tl, l[i]);
        double TL = sqrt(r * r - T.x * T.x - T.y * T.y);
        c = c * TL;
        // std::cerr << T.x << ' ' << T.y << '\n';
        if (neline(T + c, l[i])) t.push_back(T + c);
        if (neline(T - c, l[i])) t.push_back(T - c);
    }
    if (t.empty()) {
        if (in(Vector(0, r))) ans += 2 * pi;
        return ans;
    }
    for (auto &it : t) {
        it.theta = atan2(it.y, it.x);
    }
    std::sort(t.begin(), t.end());
    for (int i = 0; i < t.size(); ++i) {
        if (!(t[i] == t[(i + 1) % t.size()])) {
            ans += get(t[i], t[(i + 1) % t.size()], r);
        }
    }
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        std::cin >> p[i].x >> p[i].y;
    }
    for (int i = 1; i <= m; ++i) {
        std::cin >> l[i].u.x >> l[i].u.y;
    }
    for (int i = 1; i < m; ++i) {
        l[i].v = l[i + 1].u;
    }
    l[m].v = l[1].u;
    double ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += solve(p[i].len());
    }
    std::cout << std::fixed << std::setprecision(5) << ans / pi / 2 << '\n';
    return 0;
}
就这篇代码
https://www.luogu.com.cn/record/78248804
https://www.luogu.com.cn/record/78248830

回复

4 条回复,欢迎继续交流。

正在加载回复...