QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735211#5104. Guardians of the GalleryBananaMacWA 1ms3956kbC++2014.3kb2024-11-11 18:23:102024-11-11 18:23:11

Judging History

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

  • [2024-11-11 18:23:11]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3956kb
查看
  • [2024-11-11 18:23:10]
  • 提交

answer

/**
 * 10:43:50 11/11/24
 * point_vis
 */
// ./ICPC/Geometry/OrganizedTemplates/point_vis.cpp
//#include "Point.cpp"
/**
 * 15:15:28 9/27/24
 * Point
 */
// ./ICPC/Geometry/OrganizedTemplates/Point.cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define int long long
#define uint unsigned int
#define double long double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define nl '\n'
#define all(v) v.begin(), v.end()
#define NO (cout << "NO" << nl);
#define YES (cout << "YES" << nl);
#define F first
#define S second
#define INF LONG_LONG_MAX
#define MOD 1000000007ll
#define EPS 1e-9l
#define PI 3.14159265358979323846264338327950288L
#define pii pair<int, int>
#define X real()
#define Y imag()
#define vec vector
#define LT int T; cin >> T; while (T--)
template<typename T>
using vec2d = vector<vector<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using indexed_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

namespace Geometry {
    using ftype = double;
    using atype = double;
    const double eps = 1e-9l;
    const double pi = acos(-1.0l);
    const double e = exp(1.0L);
    const double inf = INF;
    const int iinf = LONG_LONG_MAX;
    const int prec = 25;

    ftype sqr(ftype v) { return v * v; }

    void setPrec(ostream& out = cout) {
        out << fixed << setprecision(prec);
    }

    //bool eq(const ftype& a, const ftype& b) {
    //    return a == b;
    //}
    bool eq(const ftype& a, const ftype& b) {
        return abs(a - b) < eps;
    }

    //bool ls(const ftype& a, const ftype& b) {
    //    return a < b;
    //}
    bool ls(const ftype& a, const ftype& b) {
        return (b - a) > eps;
    }

    //bool lse(const ftype& a, const ftype& b) {
    //    return a <= b;
    //}
    bool lse(const ftype& a, const ftype& b) {
        return ls(a, b) or eq(a, b);
    }

    //bool gt(const ftype& a, const ftype& b) {
    //    return a > b;
    //}
    bool gt(const ftype& a, const ftype& b) {
        return not ls(a, b) and not eq(a, b);
    }

    // Returns angle with respect to the x-axis.
    atype angle(atype x, atype y) {
        return atan2(y, x);
    }
    atype torad(atype a) { return a / 180 * pi; }
    atype todeg(atype a) { return a / pi * 180; }

    int sign(const ftype& v) {
        if (ls(0, v)) return 1;
        else if (ls(v, 0)) return -1;
        return 0;
    }

    // Orientation of 3 points forming an angle
    enum class Orientation {
        l = 1,
        r = -1,
        c = 0
    };

    // 2D point
    struct P {
        ftype x, y;
        static P polar(const ftype& r, const atype& a) {
            return {r * cos(a), r * sin(a)};
        }
        P(): x{0}, y{0} {}
        P(ftype x, ftype y): x{x}, y{y} {}
        explicit P(const complex<ftype>& p): P(p.real(), p.imag()) {}
        explicit P(const pair<ftype, ftype>& p): P(p.F, p.S) {}
        P(const P& p): P(p.x, p.y) {}
        explicit operator complex<ftype>() const {
            return {x, y};
        }
        explicit operator pair<ftype, ftype>() const {
            return {x, y};
        }
        ftype dist(const P& p) const {
            return (*this - p).abs();
        }
        atype r() const {
            return hypot(x, y);
        }
        atype a() const {
            return angle(x, y);
        }
        atype ua(const P& p) const {
            // undirected angle
            double v0 = fabs(a() - p.a()), v1 = fabs(p.ap() - ap());
            if (ls(v0, v1)) return v0;
            else return v1;
        }
        atype ap() const {
            atype res = angle(x, y);
            if (res < 0) res += 2 * pi;
            return res;
        }
        P operator-() const {
            return *this * -1;
        }
        P operator+() const {
            return *this;
        }
        P operator+=(const P& p) {
            x += p.x;
            y += p.y;
            return *this;
        }
        P operator-=(const P& p) {
            x -= p.x;
            y -= p.y;
            return *this;
        }
        P operator*=(const ftype& v) {
            x *= v;
            y *= v;
            return *this;
        }
        P operator/=(const ftype& v) {
            x /= v;
            y /= v;
            return *this;
        }
        P operator%=(const ftype& v) {
            x = fmod(x, v);
            y = fmod(y, v);
            return *this;
        }
        P operator^=(const ftype& an) {
            return *this = rotateccw(an);
        }
        P operator|=(const ftype& an) {
            return *this = rotatecw(an);
        }
        P operator|(const ftype& an) {
            P res = *this;
            res |= an;
            return res;
        }
        P operator^(const ftype& an) {
            P res = *this;
            res ^= an;
            return res;
        }
        P operator+(const P& p) const {
            P res = *this;
            res += p;
            return res;
        }
        P operator-(const P& p) const {
            P res = *this;
            res -= p;
            return res;
        }
        P operator*(const ftype& v) const {
            P res = *this;
            res *= v;
            return res;
        }
        P operator/(const ftype& v) const {
            P res = *this;
            res /= v;
            return res;
        }
        P operator%(const ftype& v) const {
            P res = *this;
            res %= v;
            return res;
        }
        bool operator==(const P& p) const {
            return eq(x, p.x) and eq(y, p.y);
        }
        bool operator<(const P& p) const {
            return eq(p.x, x) ? ls(y, p.y) : ls(x, p.x);
        }
        bool operator<=(const P& p) const {
            return *this < p or *this == p;
        }
        ftype cross(const P& b, const P& c) const {
            return (b - *this).cross(c - *this);
        }
        Orientation orientation(const P& pb, const P& pc) const {
            const P& pa = *this;
            ftype d = (pb - pa).cross(pc - pa);
            return static_cast<Orientation>(
                    ls(0, d) - ls(d, 0)
            );
        }
        ftype cross(const P& p) const {
            return x * p.y - y * p.x;
        }
        ftype dot(const P& p) const {
            return x * p.x + y * p.y;
        }
        ftype norm() const {
            return dot(*this);
        }
        atype abs() const {
            return sqrt((atype)norm());
        }
        P truncate(ftype v) const {
            // returns a vector with norm v and having same direction
            ftype k = abs();
            if (sign(k) == 0) return *this;
            v /= k;
            return {x * v, y * v};
        }
        P normalize() const {
            return truncate(1);
        }
        P normal_l() const {
            return {-y, x};
        }
        P normal_r() const {
            return {y, -x};
        }
        P rotateccw(const atype& angle, const P& ref = {0, 0}) const {
            P res;
            ftype xs = x - ref.x, ys = y - ref.y;
            res.x = ref.x + (xs * cos(angle) - ys * sin(angle));
            res.y = ref.y + (xs * sin(angle) + ys * cos(angle));
            return res;
        }
        P rotatecw(const atype& angle, const P& ref = {0, 0}) const {
            return rotateccw(-angle, ref);
        }
        friend P operator*(const ftype& v, const P& p) {
            return p * v;
        }
        friend istream& operator>>(istream& in, P& p) {
            int xv, yv;
            in >> xv >> yv;
            p = P(xv, yv);
            return in;
        }
        friend ostream& operator<<(ostream& out, const P& p) {
            setPrec(out);
            return out << "(" << p.x << ", " << p.y << ")";
        }
    };

    // basic comparison functions
    auto angleCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.a(), p1.a());
    };
    auto radiusCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.r(), p1.r());
    };
    auto stdCmp = [](const P& p0, const P& p1) -> bool {
        return p0 < p1;
    };
    auto xCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.x, p1.x);
    };
    auto yCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.y, p1.y);
    };

    // Hash function
    struct p_hash {
        static __int128 splitmix128(__int128 x) {
            // gr = 0x9e3779b97f4a7c15f39cc0605cedc835
            // c0 = 0xbf58476d1ce4e5b9a3f7b72c1e3c9e3b
            // c1 = 0x94d049bb133111ebb4093822299f31d7
            __int128 gr = 0x9e3779b97f4a7c15, c0 = 0xbf58476d1ce4e5b9, c1 = 0x94d049bb133111eb;
            gr <<= 64;
            c0 <<= 64;
            c1 <<= 64;
            gr += 0xf39cc0605cedc835;
            c0 += 0xa3f7b72c1e3c9e3b;
            c1 += 0xb4093822299f31d7;
            x += gr;
            x = (x ^ (x >> 62)) * c0;
            x = (x ^ (x >> 59)) * c1;
            return x ^ (x >> 63);
        }

        size_t operator()(const P& p) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            __int128 x = (((__int128)p.x) << 64) | ((__int128)p.y);
            return splitmix128(x + FIXED_RANDOM);
        }
    };
}
using namespace Geometry;

//如果两个向量的叉积结果符号相反（一个为正，一个为负），则说明线段AC和线段AD在线段AB的两侧，即线段AC和线段AD相交。
double RayIntersect(const P& a, const P& b, const P& c, const P& d, int* sides = NULL) {
    double cp1 = (c-a).cross(b-a), cp2 = (d-a).cross(b-a);
    double dp1 = (c-a).dot(b-a), dp2 = (d-a).dot(b-a);
    if (sides) *sides = (cp1 < -eps || cp2 < -eps) + 2 * (cp1 > eps || cp2 > eps);//sides 0,1,2,3,如果两个线段相交,一定是3  1,2是ab直线穿过c或者d的情况
    if (cp1 < -eps && cp2 < -eps || cp1 > eps && cp2 > eps) return -1.0;//叉积结果同号，线段不相交
    return (abs(cp1) < eps && abs(cp2) < eps) ? 0 : (dp1*cp2-dp2*cp1)/(cp2-cp1);//a到交点的距离乘以ab长度
}

bool POnLine(const P& a, const P& b, const P& p) {
    double ln = (b-a).abs(), cp = (b-a).cross(p-a), dp = (b-a).dot(p-a);
    return abs(cp/ln) < eps && dp/ln > -eps && dp/ln < ln+eps;//cp=0 && 0<dp<ln^2
}

int32_t main(){
    int n;
    cin>>n;
    vector<P> polygon(n);
    P s,g;
    for (int i = 0; i < n; ++i) {
        cin>>polygon[i];
    }
    cin>>g>>s;
    vector<P> endpoints;
    //找指向每个顶点方向距离最近的intersecting边
    polygon.push_back(g);//g点方向也需要找
    for(auto p:polygon){
        vector<tuple<double,int>> intersections;//交点距离，遮挡面
        if((p-s).abs()<eps)continue;
        p=(p-s)/(p-s).abs()+s;
        //找出sculpture向各个顶点出发, 不被遮挡能走的最远距离maxd，即视野不被遮挡的区域的终点(在多边形的边上)
        for(int i=0;i<n;++i){
            int side=0;
            auto d= RayIntersect(s,p,polygon[i],polygon[(i+1)%n],&side);
            if(d>-eps)
                intersections.emplace_back(d,side);
        }
        ranges::sort(intersections);
        double maxd=0;
        int sides=0;
        for(auto [d,s]:intersections){
            maxd=d;
            sides|=s;
            if(sides==3)break;
        }
        endpoints.push_back(s+(p-s)*maxd);//从sculpture出发,沿着射线,视野不被遮挡的区域的终点(在多边形的边上)
        //计算顶点p2，到sculpture发出的穿过顶点i的射线，的距离,以及交点
        for(auto p2:polygon){
            auto ortho=P(s.y-p.y,p.x-s.x)*1e5;
            auto d= RayIntersect(s,p,p2,p2+ortho);
            if(d<-eps)
                d= RayIntersect(s,p,p2,p2-ortho);
            if(d>eps && d<maxd-eps)
                endpoints.push_back(s+(p-s)*d);
        }
    }
    polygon.pop_back();
    //dijkstra算法求最短长度
    vector<P> points(polygon.size()+2+endpoints.size());
    int i=0;
    points[i++]=g;
    for(auto p:polygon)points[i++]=p;
    points[i++]=s;
    for(auto p:endpoints)points[i++]=p;
    priority_queue<pair<double,int>, vector<pair<double,int>>, greater<>> que;
    vector<double> dist(points.size(),1e20);//从g到每个节点的最短路径长度
    que.emplace(0.0,0);//从0号guard的起始位置出发
    for(i=que.top().second;i<=n;i=que.top().second){
        auto d=que.top().first;
        assert(que.size());
        que.pop();
        if(d>=dist[i])continue;
        dist[i]=d;
        for(int j=0;j<points.size();++j){
            if(i==j)continue;
            auto p1=points[i], p2=points[j];
            auto ln=(p1-p2).abs();
            if(ln<eps ||
               //如果j在poly顶点i关联的两条poly边上,可以直接沿着poly边走到j,不需要后面的包含性判断
               i>=1&&i<=n && POnLine(polygon[i-1], polygon[(i) % n], p2) ||
               i>=1&&i<=n && POnLine(polygon[i-1], polygon[(i + n - 2) % n], p2)) {
                que.emplace(d+ln,j);
                continue;
            }
            //判断p1p2是否被poly完全包含
            bool fullContained=true;
            p2=p1+(p2-p1)/ln;
            for(int k=0;k<polygon.size();++k){
                auto rd= RayIntersect(p1,p2,polygon[k],polygon[(k+1)%n]);
                if(rd>eps && rd<ln-eps) {
                    fullContained=false;
                    break;
                }
            }
            if(!fullContained)continue;
            //判断一下p1p2上任意一点是不是在poly内部，来保证p1p2全段都在poly内部。通过p1p2中点画一任意射线, 看穿过poly为奇数还是偶数次
            int cnt=0;
            p1 = p1*2/3 + p2/ 3;
            p2 = p1 + P(cos(10), sin(10));
            for(int k=0;k<n;++k){
                auto rd= RayIntersect(p1,p2,polygon[k],polygon[(k+1)%n]);
                cnt+=(rd>eps);
            }
            if(cnt%2==1)
                que.emplace(d+ln,j);
        }
    }
    cout << que.top().first << nl;
}
源文件, 语言: C++20

详细

Test #1:

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

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

result:

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

Test #2:

score: 0
Accepted
time: 1ms
memory: 3816kb

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

result:

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

Test #3:

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

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.872

result:

wrong answer 1st numbers differ - expected: '140.8722826', found: '140.8720000', error = '0.0000020'
English 繁體中文 简体中文

服务器时间: 2024-12-04 22:04:54 | 开源项目