QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397562#6734. Click the Circlewtz2333AC ✓87ms4028kbC++209.1kb2024-04-24 12:50:322024-04-24 12:50:32

Judging History

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

  • [2024-04-24 12:50:32]
  • 评测
  • 测评结果:AC
  • 用时:87ms
  • 内存:4028kb
  • [2024-04-24 12:50:32]
  • 提交

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 t1,int t2,Seg s,int u,int v) {
        int l,r;
        l = max(t1,u - d);
        r = min(t2,u);
        if(l <= r) {
            double D = dis(c,s.A);
            if(D - 2.0 * R <= 0) {
                return true;
            }  
        }
        l = max(t1,v);
        r = min(t2,v + d);
        if(l <= r) {
            double D = dis(c,s.B);
            if(D - 2.0 * R <= 0) {
                return true;
            }  
        }
        l = max(t1,u);
        r = min(t2,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 - d,t + d,s,u,v)) {
                ans ++;
            }
        }
    }// C - S.C
    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;
            }
        }
        if(check1(s1.A,u1 - d,u1,s2,u2,v2)) return true;
        if(check1(s1.B,v1,v1 + d,s2,u2,v2)) return true;
        if(check1(s2.A,u2 - d,u2,s1,u1,v1)) return true;
        if(check1(s2.B,v2,v2 + d,s1,u1,v1)) 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: 0ms
memory: 3672kb

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: 3684kb

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: 3836kb

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: 3740kb

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: 3812kb

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: 0
Accepted
time: 22ms
memory: 4020kb

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:

22721

result:

ok 1 number(s): "22721"

Test #7:

score: 0
Accepted
time: 20ms
memory: 4012kb

input:

1000 35 8
2 1037 1102 9971 9940 531 534
1 301 9951 548
1 944 9962 529
1 592 9968 537
1 262 9949 531
1 312 9971 553
1 1139 9938 550
2 325 747 9967 9970 539 544
1 810 9941 536
2 906 486 9956 9953 550 552
1 1121 9940 543
2 515 1199 9965 9953 548 552
2 537 926 9972 9949 538 547
1 1356 9967 550
1 332 996...

output:

34559

result:

ok 1 number(s): "34559"

Test #8:

score: 0
Accepted
time: 27ms
memory: 4020kb

input:

1000 472 14
1 3783 7912 938
1 3307 7801 773
1 4605 7852 592
1 2999 7886 644
1 5308 7914 865
1 4978 7842 611
2 3205 5292 7915 7915 724 835
1 6173 7919 846
2 3130 4833 7921 7853 893 906
1 3449 7854 938
2 4951 3238 7824 7897 720 874
2 4842 5378 7906 7913 683 853
2 4991 4467 7906 7830 580 779
2 5782 615...

output:

103238

result:

ok 1 number(s): "103238"

Test #9:

score: 0
Accepted
time: 30ms
memory: 3888kb

input:

1000 4 51
2 6933 7307 7777 7798 450 456
2 6444 6705 7787 7794 447 460
1 7192 7784 464
2 7865 6422 7791 7797 451 460
1 7366 7794 461
2 7364 6214 7785 7782 449 454
2 7378 7099 7801 7798 450 461
2 7961 6794 7784 7788 448 449
2 6510 7007 7787 7797 453 458
1 6517 7786 446
2 6725 7216 7797 7788 451 452
2 ...

output:

36558

result:

ok 1 number(s): "36558"

Test #10:

score: 0
Accepted
time: 23ms
memory: 3864kb

input:

1000 27 6
2 3760 3746 1523 1749 339 366
2 3738 3746 1688 1609 334 356
1 3754 1559 349
1 3761 1551 347
2 3746 3755 1667 1528 338 340
2 3754 3749 1565 1664 331 356
2 3746 3759 1653 1674 357 362
2 3753 3739 1741 1625 346 359
2 3763 3747 1701 1738 340 343
2 3742 3754 1695 1759 361 366
2 3742 3752 1654 1...

output:

36245

result:

ok 1 number(s): "36245"

Test #11:

score: 0
Accepted
time: 37ms
memory: 3924kb

input:

1000 78 150
1 6600 430 535
1 6589 476 532
2 6596 6596 430 489 530 533
2 6598 6601 469 470 529 531
1 6597 495 534
1 6597 474 533
2 6592 6599 467 465 536 538
2 6600 6596 460 484 535 537
1 6587 461 529
2 6596 6596 431 485 532 533
1 6597 465 538
2 6591 6597 429 465 530 534
1 6598 439 533
2 6596 6588 458...

output:

92999

result:

ok 1 number(s): "92999"

Test #12:

score: 0
Accepted
time: 87ms
memory: 4008kb

input:

1000 19 854
1 4584 7521 143
1 4587 7497 142
2 4587 4582 7516 7363 145 147
2 4591 4585 7360 7370 143 147
2 4582 4589 7491 7418 145 147
1 4592 7366 145
2 4587 4585 7402 7375 142 143
2 4584 4585 7392 7516 145 147
2 4584 4587 7383 7502 142 147
1 4583 7462 145
1 4592 7461 146
1 4588 7409 142
2 4591 4590 ...

output:

163887

result:

ok 1 number(s): "163887"

Test #13:

score: 0
Accepted
time: 83ms
memory: 4028kb

input:

1000 38 834
2 727 740 7904 8009 721 901
2 771 686 7753 7896 707 714
2 790 766 7801 7864 877 919
1 790 7902 874
2 709 686 7990 7998 739 760
1 666 7941 849
2 677 726 8009 7939 810 820
2 679 686 7896 7935 810 923
2 747 718 8018 7963 700 786
1 719 7987 825
1 697 7975 931
1 764 7794 847
1 659 7813 813
1 ...

output:

203301

result:

ok 1 number(s): "203301"

Test #14:

score: 0
Accepted
time: 22ms
memory: 3896kb

input:

1000 767 32
2 615 605 4677 4694 404 408
1 620 4687 421
1 617 4681 452
1 621 4687 436
2 609 608 4698 4678 404 433
2 603 620 4690 4680 391 419
2 604 609 4682 4678 405 428
1 615 4678 443
2 615 611 4678 4698 402 413
1 614 4692 450
2 601 616 4695 4692 441 442
1 614 4674 401
1 617 4697 420
1 606 4698 423
...

output:

104679

result:

ok 1 number(s): "104679"

Test #15:

score: 0
Accepted
time: 19ms
memory: 3916kb

input:

1000 68 9
1 4226 6175 121
2 4232 4221 5792 5879 82 102
1 4226 6152 69
1 4226 5910 69
2 4238 4242 6314 6215 70 74
1 4233 6208 149
1 4247 5765 162
2 4237 4221 5787 5877 180 192
1 4223 5966 148
1 4221 5925 111
2 4241 4245 6105 6069 173 203
1 4234 6275 108
1 4230 5952 166
1 4247 5925 214
1 4220 6288 192...

output:

43227

result:

ok 1 number(s): "43227"

Test #16:

score: 0
Accepted
time: 79ms
memory: 4000kb

input:

1000 20 500
2 9234 9242 4563 4578 972 976
2 9230 9142 4582 4551 972 973
1 9207 4564 971
1 9246 4561 973
2 9228 9253 4564 4571 976 977
1 9132 4566 973
2 9207 9273 4564 4582 970 982
2 9182 9172 4552 4583 965 970
2 9241 9248 4561 4564 965 966
1 9160 4570 978
1 9171 4573 978
1 9288 4564 977
2 9124 9209 ...

output:

168341

result:

ok 1 number(s): "168341"

Test #17:

score: 0
Accepted
time: 32ms
memory: 3788kb

input:

1000 479 93
2 3917 4659 8054 8309 907 919
1 3652 8108 917
1 3807 8421 889
1 3809 7956 918
2 5455 6444 8146 7993 888 897
1 3919 8428 896
1 5806 8417 904
1 5003 8284 908
1 4433 8111 900
2 4758 5119 8171 8370 893 917
1 5167 8085 909
2 5355 4401 8243 8214 894 902
2 4998 6113 8049 7961 901 905
2 6438 588...

output:

130628

result:

ok 1 number(s): "130628"

Test #18:

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

input:

1000 9 64
2 4598 4157 749 771 946 951
2 3869 4053 744 756 946 957
1 3637 785 963
2 4680 4023 760 797 949 950
2 3674 3955 743 759 949 951
1 4442 794 951
2 4336 4099 806 743 946 962
1 4544 787 962
2 4316 4548 743 802 956 963
1 3582 768 949
1 4230 794 955
2 4477 4446 778 780 957 958
2 3758 4306 751 781...

output:

35598

result:

ok 1 number(s): "35598"

Test #19:

score: 0
Accepted
time: 26ms
memory: 3796kb

input:

1000 57 27
1 7434 3356 642
2 7427 7433 3355 3354 669 684
2 7432 7435 3353 3354 683 778
1 7424 3356 772
2 7434 7421 3356 3351 727 803
2 7432 7420 3355 3352 672 695
2 7426 7421 3353 3354 630 656
2 7425 7420 3352 3355 696 701
1 7428 3352 720
1 7429 3355 692
1 7433 3353 714
1 7430 3355 838
2 7432 7420 3...

output:

61871

result:

ok 1 number(s): "61871"

Test #20:

score: 0
Accepted
time: 63ms
memory: 3756kb

input:

1000 883 463
1 2380 6779 801
2 1342 1303 6814 6780 800 801
2 263 1224 6797 6792 801 803
2 623 427 6787 6793 801 803
2 398 2034 6801 6790 802 803
1 1521 6782 800
1 1090 6807 803
1 575 6806 799
2 998 1435 6782 6788 801 803
1 811 6799 800
2 1509 1567 6783 6779 799 800
1 1156 6812 800
1 294 6802 800
1 1...

output:

522826

result:

ok 1 number(s): "522826"

Test #21:

score: 0
Accepted
time: 77ms
memory: 3788kb

input:

1000 1 430
2 9469 9548 8535 8853 127 180
1 9510 9271 108
1 9417 9255 118
1 9603 9094 127
1 9416 8441 120
2 9591 9501 9100 9100 147 198
2 9413 9551 8606 8240 216 223
2 9506 9525 8715 9157 80 152
1 9559 8977 42
1 9552 9286 54
2 9555 9551 8424 9279 37 131
1 9376 9085 61
2 9488 9543 9140 9374 87 222
2 9...

output:

59834

result:

ok 1 number(s): "59834"

Test #22:

score: 0
Accepted
time: 16ms
memory: 3772kb

input:

1000 49 3
2 8881 8913 1885 2159 225 239
1 8883 1980 245
2 8908 8883 2082 2199 223 254
2 8903 8905 2170 2048 229 247
1 8882 1944 225
1 8910 1844 247
2 8887 8902 2034 2080 232 233
1 8887 2082 250
1 8901 1908 251
2 8899 8884 1884 2112 242 245
1 8889 1914 254
1 8899 2188 250
2 8908 8881 2071 2019 239 24...

output:

24042

result:

ok 1 number(s): "24042"

Test #23:

score: 0
Accepted
time: 75ms
memory: 3808kb

input:

1000 51 968
1 3531 6961 345
1 4472 7149 357
1 2691 6615 359
2 3325 4548 7314 6828 356 358
2 4801 3905 6987 6647 358 372
1 4974 6876 366
1 4527 6792 344
2 3363 3335 7054 7147 359 365
1 2922 6705 375
1 4487 7293 355
2 3236 4914 6926 6782 346 374
1 4463 6740 369
1 2796 6833 361
1 3969 6830 358
1 4665 7...

output:

274214

result:

ok 1 number(s): "274214"

Test #24:

score: 0
Accepted
time: 19ms
memory: 3892kb

input:

1000 1 10
2 5234 5378 7146 7016 658 806
2 3852 5355 6863 6990 837 883
2 3953 3596 7007 6909 701 756
1 6504 6967 920
2 4033 5760 6873 7090 674 869
2 4163 4267 7178 6938 864 912
1 3622 6948 938
1 5798 7146 824
1 4829 7126 786
1 4400 6989 775
1 4738 6933 854
2 4230 5240 6863 7148 711 796
1 3987 7172 84...

output:

15333

result:

ok 1 number(s): "15333"

Test #25:

score: 0
Accepted
time: 28ms
memory: 3808kb

input:

1000 614 50
2 2448 2538 7136 7095 541 552
1 2348 7052 565
1 2498 7085 554
2 2313 2444 7132 7152 552 564
1 2300 7021 560
1 2289 7066 553
2 2572 2547 7122 7067 551 563
2 2473 2462 7054 7062 556 563
1 2290 7046 553
2 2397 2493 7134 7053 547 550
1 2312 7049 551
2 2595 2448 7085 7113 549 557
2 2432 2314 ...

output:

133247

result:

ok 1 number(s): "133247"