QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397546#6734. Click the Circlewtz2333WA 16ms3932kbC++208.9kb2024-04-24 12:14:292024-04-24 12:14:31

Judging History

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

  • [2024-04-24 12:14:31]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:3932kb
  • [2024-04-24 12:14:29]
  • 提交

answer

#include <bits/stdc++.h>
#define double long double
using namespace std;
typedef long long ll;
constexpr double eps = 1e-9;
constexpr double PI = acos(-1);
constexpr double inf = 1e9;
struct Point { 
    double x, y;
};        // 点
using Vec = Point;                    // 向量
struct Line { Point P; Vec v; };      // 直线(点向式),射线时为A->B
struct Seg { 
    Point A, B; 
};           // 线段(存两个端点)
struct Circle { Point O; double r; }; // 圆(存圆心和半径)
using Points = std::vector<Point>;
using ConvexHull = std::vector<Point>;
const Point O = {0, 0};                        // 原点
const Line Ox = {O, {1, 0}}, Oy = {O, {0, 1}}; // 坐标轴

bool eq(double a, double b) { return abs(a - b) <= 0; } // ==
bool gt(double a, double b) { return a - b > eps; }      // >
bool lt(double a, double b) { return a - b < -eps; }     // <
bool ge(double a, double b) { return a - b > -eps; }     // >=
bool le(double a, double b) { return a - b <= 0; }      // <=
Vec operator + (const Vec &a,const Vec &b){return (Vec){a.x + b.x,a.y + b.y};}
Vec operator - (const Vec &a,const Vec &b){return (Vec){a.x - b.x,a.y - b.y};}
Vec operator * (const Vec &a,const double &b){return (Vec){b * a.x,b * a.y};}
Vec operator * (const double &a,const Vec &b){return (Vec){a * b.x,a * b.y};}
Vec operator / (const Vec &a,const double &b){return (Vec){a.x / b,a.y / b};}
double operator * (const Point &a,const Point &b){return a.x * b.x + a.y * b.y;}// dot // 点乘
double operator ^ (const Point &a,const Point &b){return a.x * b.y - a.y * b.x;}// cross  // 叉乘
bool operator < (const Point& a, const Point& b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
double len(const Vec &a){return sqrt(a * a);}

int sgn(double x){
    if(fabs(x) <= 0)
        return 0;
    if(x < 0)
        return -1;
    return 1;
}

Line line(Point A, Point B) { return {A, B - A}; }

// 斜截式直线
Line line(double k, double b) { return {{0, b}, {1, k}}; }

// 点斜式直线
Line line(Point P, double k) { return {P, {1, k}}; }

// 线段所在直线
// DEPENDS V-V
Line line(Seg l) { return {l.A, l.B - l.A}; }


// 两点间的距离
// DEPENDS len, V-V
double dis(Point A, Point B) { return len(A - B); }

// 点到直线的距离
// DEPENDS V^V, len
double dis(Point P, Line l) { return fabs((P ^ l.v) - (l.P ^ l.v)) / len(l.v); }

// 点到线段的距离
double dis(Point P,Seg l) {
    // cerr << "ASDfasdfasd\n";
    if(((P - l.A) * (l.B - l.A)) <= 0 || ((P - l.B) * (l.A - l.B)) <= 0){
        // cerr << "!!!asdafd\n";
        return min(dis(P,l.A),dis(P,l.B));
    }else {
        Line l1 = line(l);
        return dis(P,l1);
    }
}

// 线段与线段是否相交
bool cross_seg(Seg A,Seg B){
    Point a = A.A,b = A.B,c = B.A,d = B.B;
    double c1 = (b - a) ^ (c - a),c2 = (b - a) ^ (d - a);
    double d1 = (d - c) ^ (a - c),d2 = (d - c) ^ (b - c);
    return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;
}

int main() {
    int n,d,R;
    cin >> n >> R >> d;
    vector<pair<Point,int>> C;
    vector<tuple<Seg,int,int>> S;
    int ans = 0;
    for(int i = 0;i < n;i ++) {
        int opt;
        cin >> opt;
        if(opt == 1) {
            double x,y;
            int t;
            cin >> x >> y >> t;
            C.push_back({Point{x,y},t});
        }else {
            Point s,t;
            int u,v;
            cin >> s.x >> s.y >> t.x >> t.y >> u >> v;
            S.push_back(make_tuple(Seg{s,t},u,v));
            ans ++;
        }
    }
    for(int i = 0;i < C.size();i ++) {
        for(int j = i + 1;j < C.size();j ++) {
            auto [c1,t1] = C[i];
            auto [c2,t2] = C[j];
            int l = max(t1 - d,t2 - d);
            int r = min(t1 + d,t2 + d);
            if(l > r) continue;
            double D = dis(c1,c2);
            // cerr << D - 2.0 * R << endl;
            if(D - 2.0 * R <= 0) {
                ans ++;
            }
        }
    }// C - C
    for(auto [c,t]:C) {
        for(auto [s,u,v]:S) {
            int l = max(t - d,u - d);
            int r = min(t + d,v + d);
            if(l > r)continue;
            double D = dis(c,s);
            if(D - 2.0 * R <= 0) {
                ans ++;
            }
        }
    } // C - S.f
    auto disss = [&](Seg a,Seg b) -> double {
        if(cross_seg(a,b)) return 0.0;
        double D = min({dis(a.A,b),dis(a.B,b),dis(b.A,a),dis(b.B,a)});
        return D;
    };
    for(int i = 0;i < S.size();i ++) {
        auto [s1,u1,v1] = S[i];
        for(int j = i + 1;j < S.size();j ++) {
            auto [s2,u2,v2] = S[j];
            int l = max(u1 - d,u2 - d);
            int r = min(v1 + d,v2 + d);
            if(l > r) continue;
            double D = disss(s1,s2);  
            if(D - 2.0 * R <= 0) {
                ans ++;
            }  
        }
    }// S.f - S.f
    auto check0 = [&](Seg s1,int u1,int v1,Seg s2,int u2,int v2) {
        int l,r;
        l = max(u1 - d,u2);
        r = min(v1 + d,v2);
        if(l <= r) {
            Seg tmp2;
            tmp2.A = s2.A + (s2.B - s2.A) * (l - u2) / (v2 - u2);
            tmp2.B = s2.A + (s2.B - s2.A) * (r - u2) / (v2 - u2);
            double D = disss(s1,tmp2);  
            if(D - 2.0 * R <= 0) {
                return true;
            }  
        }
        l = max(u1 - d,u2 - d);
        r = min(v1 + d,u2);
        if(l <= r) {
            double D = dis(s2.A,s1);  
            if(D - 2.0 * R <= 0) {
                return true;
            }  
        }
        l = max(u1 - d,v2);
        r = min(v1 + d,v2 + d);
        if(l <= r) {
            double D = dis(s2.B,s1);  
            if(D - 2.0 * R <= 0) {
                return true;
            }  
        }
        return false;
    };
    for(int i = 0;i < S.size();i ++) {
        auto [s1,u1,v1] = S[i];
        for(int j = 0;j < S.size();j ++) {
            if(j == i) continue;
            auto [s2,u2,v2] = S[j];
            if(check0(s1,u1,v1,s2,u2,v2)) {
                ans ++;
            }
        }
    }// S.f - S.C
    auto check1 = [&](Point c,int t,Seg s,int u,int v) {
        int l,r;
        l = max(t - d,u - d);
        r = min(t + d,u);
        if(l <= r) {
            double D = dis(c,s.A);
            if(D - 2.0 * R <= 0) {
                return true;
            }  
        }
        l = max(t - d,v);
        r = min(t + d,v + d);
        if(l <= r) {
            double D = dis(c,s.B);
            if(D - 2.0 * R <= 0) {
                return true;
            }  
        }
        l = max(t - d,u);
        r = min(t + d,v);
        if(l <= r) {
            Seg tmp;
            tmp.A = s.A + (s.B - s.A) * (l - u) / (v - u);
            tmp.B = s.A + (s.B - s.A) * (r - u) / (v - u);

            double D = dis(c,tmp);
            if(D - 2.0 * R <= 0) {
                return true;
            }  
        }
        return false;
    };
    for(auto [c,t]:C) {
        for(auto [s,u,v]:S) {
            if(check1(c,t,s,u,v)) {
                ans ++;
            }
        }
    }// C - S.C
    // cerr << "asdfasdf\n";
    auto check2 = [&](Seg s1,int u1,int v1,Seg s2,int u2,int v2) {
        int l,r;
        l = max(u1 - d,u2 - d);
        r = min(u1,u2);
        if(l <= r) {
            double D = dis(s1.A,s2.A);
            if(D - 2.0 * R <= 0) {
                return true;
            }
        }
        l = max(v1,v2);
        r = min(v1 + d,v2 + d);
        if(l <= r) {
            double D = dis(s1.B,s2.B);
            if(D - 2.0 * R <= 0) {
                return true;
            }
        }
        l = max(u1 - d,v2);
        r = min(u1,v2 + d);
        if(l <= r) {
            double D = dis(s1.A,s2.B);
            if(D - 2.0 * R <= 0) {
                return true;
            }
        }
        l = max(v1,u2 - d);
        r = min(v1 + d,u2);
        if(l <= r) {
            double D = dis(s1.B,s2.A);
            if(D - 2.0 * R <= 0) {
                return true;
            }
        }
        l = max(u1,u2);
        r = min(v1,v2);
        if(l <= r){
            Seg tmp1;
            tmp1.A = s1.A + (s1.B - s1.A) * (l - u1) / (v1 - u1);
            tmp1.B = s1.A + (s1.B - s1.A) * (r - u1) / (v1 - u1);
            Seg tmp2;
            tmp2.A = s2.A + (s2.B - s2.A) * (l - u2) / (v2 - u2);
            tmp2.B = s2.A + (s2.B - s2.A) * (r - u2) / (v2 - u2);
            Seg tmp = {tmp1.A - tmp2.A,tmp1.B - tmp2.B};
            double D = dis(O,tmp);
            if(D - 2.0 * R <= 0) {
                return true;
            }
        }
        return false;
    };
    for(int i = 0;i < S.size();i ++) {
        auto [s1,u1,v1] = S[i];
        for(int j = i + 1;j < S.size();j ++) {
            auto [s2,u2,v2] = S[j];
            if(check2(s1,u1,v1,s2,u2,v2)) {
                ans ++;
            }  
        }
    }// S.C - S.C
    cout << ans << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 1 1
1 1 1 2
1 2 2 3

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 1 1
1 1 1 2
1 3 2 3

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

2 1 1
1 3 3 2
2 5 5 5 1 2 4

output:

3

result:

ok 1 number(s): "3"

Test #4:

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

input:

2 1 1
2 1 1 1 5 2 4
2 5 5 5 1 2 4

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

2 1 1
2 10 1 10 20 2 4
2 1 10 20 10 2 4

output:

6

result:

ok 1 number(s): "6"

Test #6:

score: -100
Wrong Answer
time: 16ms
memory: 3812kb

input:

1000 8 4
1 8323 2820 943
1 8246 2850 944
1 8177 2880 941
1 8154 2866 944
2 8325 8146 2865 2846 943 944
1 8349 2891 939
2 8176 8344 2888 2692 940 945
1 8191 2732 945
1 8144 2668 945
2 8182 8191 2889 2844 939 940
1 8173 2687 941
1 8241 2870 945
2 8266 8344 2910 2667 942 943
1 8169 2863 939
1 8349 2921...

output:

22540

result:

wrong answer 1st numbers differ - expected: '22721', found: '22540'