QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354683#5104. Guardians of the GalleryJerryTclWA 1ms3968kbC++205.3kb2024-03-15 21:03:362024-03-15 21:03:37

Judging History

你现在查看的是最新测评结果

  • [2024-03-15 21:03:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3968kb
  • [2024-03-15 21:03:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
template<typename T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using MaxHeap = priority_queue<T, vector<T>, less<T>>;
constexpr double eps = 1e-9;
int dSgn(double x) { return x < -eps ? -1 : x > eps ? 1 : 0; }
int dCmp(double x, double y) { return dSgn(x - y);  }
template<int CloseR = 1, int CloseL = 1> int dIn(double x, double l, double r)
    { return (CloseL ? l - eps : l + eps) < x && x < (CloseR ? r + eps : r - eps); }
typedef struct Pnt { double x, y; } Vec;
using cPnt = const Pnt; using cVec = const Vec;
inline Vec operator + (cVec a, cVec b) { return {a.x + b.x, a.y + b.y}; }
inline Vec operator - (cVec a, cVec b) { return {a.x - b.x, a.y - b.y}; }
inline Vec operator * (cVec a, const double b) { return {a.x * b, a.y * b}; }
inline Vec operator / (cVec a, const double b) { return {a.x / b, a.y / b}; }
inline int operator == (cPnt a, cPnt b) { return !dCmp(a.x, b.x) && !dCmp(a.y, b.y); }
inline int operator != (cPnt a, cPnt b) { return dCmp(a.x, b.x) || dCmp(a.y, b.y); }
inline double Dot(cVec a, cVec b) { return a.x * b.x + a.y * b.y; }
inline double Cro(cVec a, cVec b) { return a.x * b.y - a.y * b.x; }
inline double Len2(cVec a) { return Dot(a, a); }
inline istream &operator >> (istream &in, Pnt &p) { return in >> p.x >> p.y; }
inline int In(cPnt p, cPnt a, cPnt b) {
    cVec PA = a - p, PB = b - p;
    return !dSgn(Cro(PA, PB)) && dSgn(Dot(PA, PB)) <= 0;
}
struct Polygon : vector<Pnt> {
    Polygon(int n) : vector<Pnt>(n) {}
    int nxtp(int x) const { return x + 1 == (int)size() ? 0 : x + 1; }
    template<int Tp = 0> void getXs(vector<Pnt> &ret, cPnt u, cPnt v) const {
        for(int i = 0; i < (int)size(); ++i) {
            cPnt p = (*this)[i], q = (*this)[nxtp(i)];
            cVec UV = v - u, PU = u - p, PV = v - p, PQ = q - p;
            if(!dSgn(Cro(UV, PQ))) continue;
            const double area0 = Cro(PU, PQ), area1 = Cro(PV, PQ);
            if(!area0 || !area1) continue;
            cPnt C = u + UV * (area0 / (area0 - area1));
            if(In(C, p, q) && (Tp || (p != C && q != C))) ret.push_back(C);
        }
    }
    int containLine(cPnt u, cPnt v) const {
        static vector<Pnt> buf; buf.clear(), getXs(buf, u, v);
        for(cPnt p : buf) if(In(p, u, v)) return 0;
        cPnt mid = (u + v) * .5; int ret = 0;
        for(int i = 0; i < (int)size(); ++i) {
            cPnt p = (*this)[i], q = (*this)[nxtp(i)];
            if(In(mid, p, q)) return 1; if(p.y == q.y) continue;
            if(p.y < q.y && dIn<0>(mid.y, p.y, q.y))
                ret += dSgn(Cro(q - p, mid - p)) == 1;
            if(p.y > q.y && dIn<0>(mid.y, q.y, p.y))
                ret += dSgn(Cro(p - q, mid - q)) == 1;
        }
        return ret & 1;
    }
};
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n; Polygon pg(n); Pnt goal;
    for(int i = 0; i < n; ++i) cin >> pg[i];
    vector<pair<Pnt, double>> keys(n + 1);
    cin >> keys[0].fi >> goal, keys[0].se = 1e18;
    for(int i = 1; i <= n; ++i) keys[i] = {pg[i - 1], 1e18};
    const auto &check = [&](cPnt x) {
        int l = 0, r = 0;
        for(int i = 0; i < (int)pg.size(); ++i) {
            cPnt p = pg[i], q = pg[pg.nxtp(i)];
            if(In(p, x, goal) && x != p) {
                const int w = dSgn(Cro(x - goal, q - goal));
                if(w) { w == 1 ? ++l : ++r; if(l && r) return 0; }
            }
            if(In(q, x, goal) && x != q) {
                const int w = dSgn(Cro(x - goal, p - goal));
                if(w) { w == 1 ? ++l : ++r; if(l && r) return 0; }
            }
        }
        return 1;
    };
    const auto &checkpnt = [&](cPnt p) {
        return pg.containLine(p, goal) && check(p); };
    for(int i = 0; i <= n; ++i) if(checkpnt(keys[i].fi)) {
        static vector<Pnt> buf; keys[i].se = 0;
        buf.clear(), pg.getXs<1>(buf, keys[i].fi, goal);
        pair<double, int> mn = {1e18, -1};
        for(int j = 0; j < (int)buf.size(); ++j) {
            double l = buf[j].x, r = goal.x; if(l > r) swap(l, r);
            if(dIn(keys[i].fi.x, l, r)) mn = \
                min(mn, {Len2(keys[i].fi - buf[j]), j});
        }
        if(mn.se != -1 && check(buf[mn.se])) keys.emplace_back(buf[mn.se], 0);
    }
    const int z = (int)keys.size();
    for(int i = 0; i < z; ++i) if(keys[i].se == 0) {
        cPnt P = keys[i].fi; cVec OP = P - goal;
        const double len2 = Len2(OP), len = sqrt(len2);
        for(int j = 0; j < z; ++j) {
            cPnt Q = keys[j].fi; cVec OQ = Q - goal;
            const double fr = Dot(OP, OQ) / len2;
            if(!dIn(fr, 0, 1)) continue;
            if(pg.containLine(Q, goal + OP * fr))
                keys[j].se = min(keys[j].se, abs(Cro(OP, OQ)) / len);
        }
    }
    MinHeap<pair<double, int>> Q;
    for(int i = 0; i < z; ++i) Q.emplace(keys[i].se, i);
    while(!Q.empty() && Q.top().se) {
        const auto [d, u] = Q.top(); Q.pop();
        if(keys[u].se != d) continue;
        for(int v = 0; v < z; ++v) {
            const double len = sqrt(Len2(keys[u].fi - keys[v].fi));
            if(d + len < keys[v].se && pg.containLine( \
                keys[u].fi, keys[v].fi)) Q.emplace(keys[v].se = d + len, v);
        }
    }
    printf("%.13lf", keys[0].se);
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3924kb

input:

15
13 7
20 20
39 20
49 7
73 13
100 5
117 38
98 20
80 20
66 40
68 20
51 20
41 39
22 48
2 39
10 20
104 20

output:

29.0000000000000

result:

ok found '29.0000000', expected '29.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

16
39 2
48 22
39 41
20 51
20 68
40 66
20 80
20 98
38 117
5 100
13 73
7 49
19 39
20 23
20 20
7 13
20 10
20 104

output:

13.0000000000000

result:

ok found '13.0000000', expected '13.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

16
13 33
20 60
23 66
39 97
49 105
73 166
100 205
117 272
98 216
80 180
66 172
68 156
51 122
41 121
22 92
2 44
10 40
104 228

output:

140.8722825824867

result:

ok found '140.8722826', expected '140.8722826', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3964kb

input:

16
64 17
50 28
67 23
65 18
77 4
88 20
78 10
70 29
61 28
47 32
54 17
43 13
35 20
41 30
27 20
42 6
81 12
33 23

output:

60.2776755407364

result:

wrong answer 1st numbers differ - expected: '64.2045377', found: '60.2776755', error = '0.0611618'