QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#515665#2268. Solar CarIllusionaryDominanceTL 1ms6452kbC++203.2kb2024-08-11 20:18:532024-08-11 20:18:54

Judging History

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

  • [2024-08-11 20:18:54]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:6452kb
  • [2024-08-11 20:18:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define y1 fuckcpp

const int MAX_N = 2000 + 5;
const double Pi = acos(-1);

int N, Q;
struct Node{
    int x, y, id;
    double angle;
    
    Node () {}
    Node (int x_, int y_, int id_) {
        x = x_; y = y_; id = id_;
        angle = atan2(y, x);
    }
    
    inline bool operator < (const Node &comp) const {
        return angle < comp.angle;
    }
}node[MAX_N];
double ans[MAX_N][MAX_N], dis[MAX_N][MAX_N];

bool check_pi(double x, double y) {
    // x in [y, y+Pi]
    if (y < -Pi) y += Pi * 2;
    if (y < 0) {
        return x >= y && x <= y + Pi;
    }
    return (x >= y || x <= y - Pi);
}

double query(int lx, int rx, int ly, int ry) {
    return ans[rx][ry] - ans[rx][ly - 1] - ans[lx - 1][ry] + ans[lx - 1][ly - 1];
}

double calc_dis(int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double calc_dis(int i, int j) {
    return calc_dis(node[i].x, node[i].y, node[j].x, node[j].y);
}

bool leftOf(int i, int j, int k) {
    // j is left of ik
    return (node[k].x - node[i].x) * (node[j].y - node[i].y) >= (node[k].y - node[i].y) * (node[j].x - node[i].x);
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        node[i] = Node(x, y, i);
    }
    sort(node + 1, node + N + 1);
    for (int i = 1; i <= N; i ++) {
        // counter-clockwise
        static int sta[MAX_N];
        int tp = 0; double len = 0;
        sta[++ tp] = i;
        for (int j = (i < N ? i + 1 : 1); j != i && check_pi(node[j].angle, node[i].angle); j = (j < N ? j + 1 : 1)) {
            while (tp > 1 && leftOf(sta[tp - 1], j, sta[tp])) {
                len -= calc_dis(sta[tp - 1], sta[tp]);
                tp --;
            }
            len += calc_dis(sta[tp], j);
            sta[++ tp] = j;
            dis[node[i].id][node[j].id] = len;
        }
        // clockwise
        tp = 0; len = 0; sta[++ tp] = i;
        for (int j = (i > 1 ? i - 1 : N); j != i && check_pi(node[j].angle, node[i].angle - Pi); j = (j > 1 ? j - 1 : N)) {
            while (tp > 1 && leftOf(sta[tp - 1], sta[tp], j)) {
                len -= calc_dis(sta[tp - 1], sta[tp]);
                tp --;
            }
            len += calc_dis(sta[tp], j);
            sta[++ tp] = j;
            dis[node[i].id][node[j].id] = len;
        }
    }
    for (int i = 1; i <= N; i ++) {
        for (int j = i; j <= N; j ++) {
            assert(abs(dis[i][j] - dis[j][i]) <= 1);
            for (int k = 1; k <= N; k ++) {
                ans[i][j] = max(ans[i][j], dis[i][k] + dis[k][j]);
            }
            ans[j][i] = ans[i][j];
        }
    }
    for (int i = 1; i <= N; i ++) {
        for (int j = 1; j <= N; j ++) {
            ans[i][j] += ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1];
        }
    }
    scanf("%d", &Q);
    while (Q --) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        printf("%.10lf\n", query(a, b, c, d) / (b - a + 1) / (d - c + 1));
    }
    return 0;
}

/*
5
7 0
3 3
0 7
-3 3
-7 0
6
1 1 3 3
3 3 4 4
1 1 5 5
5 5 2 2
2 2 4 4
1 5 1 5
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4348kb

input:

5
7 0
3 3
0 7
-3 3
-7 0
6
1 1 3 3
3 3 4 4
1 1 5 5
5 5 2 2
2 2 4 4
1 5 1 5

output:

24.0000000000
20.4403065089
20.0000000000
19.0000000000
15.4403065089
21.6065716450

result:

ok 6 numbers

Test #2:

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

input:

3
186 689
716 695
247 -231
133
1 2 1 3
1 3 2 2
3 3 2 2
2 2 3 3
1 2 1 2
1 2 3 3
1 3 3 3
2 3 3 3
2 2 3 3
1 3 2 2
1 2 3 3
1 2 2 2
1 1 3 3
1 2 1 2
1 1 1 2
1 2 2 2
3 3 2 3
2 2 2 3
1 3 1 3
2 3 1 3
1 2 1 3
1 2 1 2
1 2 2 2
3 3 1 2
1 2 1 3
2 2 1 2
2 2 1 2
1 2 1 3
1 2 1 3
1 3 2 2
1 3 1 2
3 3 1 3
3 3 2 2
1 3 2...

output:

1810.0252312113
1829.3546584226
1452.0540260337
1452.0540260337
1960.0166929831
1510.0423076676
1698.6926238621
1764.0236411424
1452.0540260337
1829.3546584226
1510.0423076676
2018.0049746171
1568.0305893016
1960.0166929831
1902.0284113492
2018.0049746171
1764.0236411424
1764.0236411424
1772.9143620...

result:

ok 133 numbers

Test #3:

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

input:

3
995 866
-744 999
-528 -207
133
1 2 2 3
2 3 2 3
1 2 2 3
1 2 1 3
1 2 3 3
2 2 2 2
1 3 1 3
3 3 3 3
1 1 2 3
3 3 3 3
1 3 1 1
1 1 3 3
1 2 2 3
2 3 1 2
1 3 1 1
3 3 2 3
1 1 2 3
2 3 1 3
1 2 1 3
1 1 2 2
1 3 1 3
1 1 1 2
1 1 3 3
1 3 1 1
2 2 1 2
2 2 1 3
1 2 1 3
1 2 2 3
2 3 2 2
1 3 1 2
1 2 2 3
1 3 2 3
2 3 1 2
1 3...

output:

3288.1857950114
3607.1024393287
3288.1857950114
3327.8342392698
3288.1857950114
3488.1571065535
3363.2694219717
3726.0477721038
3028.7418170817
3726.0477721038
3261.1771354224
2969.2691506942
3288.1857950114
3288.1857950114
3261.1771354224
3666.5751057163
3028.7418170817
3414.3155652464
3327.8342392...

result:

ok 133 numbers

Test #4:

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

input:

3
-630 864
896 -31
-359 -691
133
1 3 1 2
1 2 1 2
2 3 2 3
1 2 2 2
1 3 1 3
2 3 2 2
1 3 1 3
1 2 1 1
1 2 1 1
1 2 2 2
1 1 1 3
1 2 1 2
2 2 1 2
2 2 2 3
2 2 2 2
3 3 1 2
1 1 3 3
2 3 1 2
3 3 1 2
1 2 2 3
2 2 2 3
1 2 3 3
2 3 1 3
2 3 2 3
1 2 1 3
1 2 1 3
3 3 2 3
3 3 2 3
2 3 1 3
1 2 1 2
2 3 1 3
3 3 2 2
2 3 1 2
1 2...

output:

3267.2975601703
3267.2975601703
3347.5339322107
3267.2975601703
3255.0284613357
3442.8630629865
3255.0284613357
3267.2975601703
3267.2975601703
3267.2975601703
3240.5521028235
3267.2975601703
3267.2975601703
3442.8630629865
3538.1921937622
3267.2975601703
3187.0611881298
3267.2975601703
3267.2975601...

result:

ok 133 numbers

Test #5:

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

input:

7
342 -176
53 -703
-687 -627
-580 -95
741 -873
249 47
125 -989
133
2 3 7 7
1 6 1 2
3 6 2 5
4 5 5 7
6 7 3 3
2 4 2 3
1 4 2 5
1 6 1 5
4 5 3 5
1 4 3 3
1 4 1 7
6 7 1 4
3 7 4 5
6 7 2 5
1 5 1 7
1 2 4 6
6 6 1 2
1 3 1 6
3 7 5 7
1 3 1 5
3 7 3 6
2 6 2 5
1 5 2 4
3 4 1 5
3 5 1 2
4 7 3 7
5 7 1 3
3 6 2 6
2 6 2 6
2...

output:

2123.5654111090
2157.7662599915
2486.7414907458
2518.4688725726
2347.0683758134
2368.4242335419
2383.9799238214
2365.0580037650
2551.1004855317
2576.9537396779
2309.5957367223
2227.3389482150
2535.6024323304
2336.3983736128
2349.3367058682
2289.8413315992
2087.1114824953
2272.0273840338
2423.4235397...

result:

ok 133 numbers

Test #6:

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

input:

7
105 906
969 -998
68 -422
154 -468
558 785
-849 652
-949 181
133
4 7 2 5
1 6 5 7
5 6 2 7
4 5 4 6
1 4 1 6
2 2 5 7
4 5 4 5
4 6 4 6
6 7 1 6
2 3 3 5
5 7 3 5
6 7 1 6
1 4 3 7
1 6 1 7
3 5 7 7
1 2 2 7
2 5 1 2
4 5 4 5
4 5 3 4
1 6 1 2
5 7 1 2
1 4 1 5
1 5 2 4
4 4 6 7
5 7 2 4
4 4 5 6
3 6 1 4
1 5 5 5
6 7 5 6
3 ...

output:

3419.3706439869
3812.4218464760
3817.9263407732
3368.6827761322
3511.2360575200
3523.9333576428
3124.9801152153
3648.2796487240
3922.2417478045
3390.1660283126
3482.2431054522
3922.2417478045
3420.3794626940
3640.3156813583
3542.4906023823
3822.6846490438
3785.8875717685
3124.9801152153
2934.7040796...

result:

ok 133 numbers

Test #7:

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

input:

7
-205 -75
-380 34
-656 57
-524 -22
907 -537
974 -975
-444 11
133
2 6 3 7
4 4 1 2
1 7 1 6
3 4 1 3
2 5 6 6
2 7 2 3
3 5 7 7
3 4 2 3
4 4 1 7
2 6 2 3
2 4 2 4
3 4 1 6
3 5 1 3
6 7 5 6
1 4 6 7
3 6 3 5
3 4 3 7
1 2 6 7
5 7 5 6
2 7 1 4
1 4 4 7
5 5 3 5
3 6 5 6
1 5 2 2
6 7 2 3
2 6 3 6
1 5 3 6
3 6 1 5
3 4 4 4
3 ...

output:

2964.9150025783
3392.9648031752
2955.5799516956
3589.3626877222
2559.0672116383
3152.3805919427
3138.5587611599
3702.2135161944
3173.0373176250
3071.0444121678
3633.4922506721
3161.0911461296
3134.6669423372
2972.2819232389
2864.3285267083
2974.3810067367
3130.1435963183
2825.8642424269
3144.7641980...

result:

ok 133 numbers

Test #8:

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

input:

20
-12 -703
-485 148
644 -768
-128 454
305 935
249 -348
414 218
-754 -626
-581 -392
35 -251
942 634
505 -888
136 -33
917 639
270 -334
775 247
688 -571
-395 -803
147 864
820 5
133
4 5 9 11
7 14 6 11
10 18 4 6
12 20 7 11
5 6 13 16
7 18 2 20
1 7 5 6
9 13 5 11
1 5 7 13
1 6 13 16
6 11 13 18
6 15 17 18
15...

output:

3142.3819356250
3244.4306671691
3118.2830694892
3298.2156693122
3108.4214285295
3287.5420798855
3125.9839835884
3220.5019331089
3239.2294433171
3074.0844575879
3215.7873445081
3440.9312398020
3341.6133390668
3166.1853402547
3239.8651316910
3298.4838170748
3304.0527210609
3160.1425928684
3255.1499428...

result:

ok 133 numbers

Test #9:

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

input:

20
59 681
418 -537
696 884
-944 -410
435 738
896 -753
300 -796
-204 19
-820 134
610 -173
-553 574
501 610
726 353
16 -339
128 875
-386 -261
-320 346
129 531
-663 877
217 92
133
7 15 16 20
4 8 20 20
3 15 15 17
12 18 7 13
4 7 16 19
2 15 7 14
17 20 15 16
2 10 10 19
5 19 2 7
7 14 7 15
5 17 15 19
9 12 10...

output:

3234.0060401531
3019.8433036951
3357.5857640875
3283.7825801558
3471.4858273218
3390.7227634253
3270.8446504081
3417.0898022187
3553.6278437820
3302.1191013409
3364.3842672683
3430.6647159703
3534.0362885830
3650.1579836785
3353.9031771890
3271.6437494408
3161.8417260673
3524.1500758856
3558.2331124...

result:

ok 133 numbers

Test #10:

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

input:

20
-837 381
-268 -208
-401 -372
-753 -220
817 -213
-505 946
-408 540
-780 -47
781 -16
444 312
869 951
22 699
-379 451
-554 -149
54 -782
-520 298
429 -33
511 613
500 374
-702 286
133
6 10 4 14
8 17 5 13
3 16 9 14
10 18 5 17
8 19 12 19
2 5 4 19
1 6 6 7
6 15 18 19
6 20 1 2
4 14 7 12
13 18 5 6
4 16 10 1...

output:

3120.7723453779
3078.1299373936
3072.3118122405
3042.7845912009
2942.4171030323
3199.1772020834
3305.7050146073
2876.8329029494
3128.7429951092
3102.8485286535
3207.2794338292
3052.9321312831
3043.9381565200
2818.1566125246
3138.0534903187
3171.3930460818
3211.9586920725
3128.7019712244
3279.8180227...

result:

ok 133 numbers

Test #11:

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

input:

20
335 432
-842 945
718 377
-611 69
547 782
63 254
-853 746
-976 -43
-129 291
-500 -921
653 -403
-20 -937
981 806
251 426
829 637
-195 435
287 691
-794 -911
-415 -259
-936 -541
133
4 18 11 18
9 18 9 17
11 14 9 13
5 17 1 15
13 20 7 15
12 13 4 16
4 18 11 18
5 11 2 9
2 10 16 20
8 20 16 19
3 20 1 11
4 1...

output:

3800.4149378241
3778.6457140530
3915.6837620962
3735.9552918473
3836.8204274557
4034.0843118186
3800.4149378241
3623.9827429292
3747.4318012922
3697.2533977362
3683.6411637134
3659.0913390773
3864.9025521018
3807.5851466675
3777.7259597087
3596.4901034632
3738.0618785695
3841.1007534420
3713.4803807...

result:

ok 133 numbers

Test #12:

score: -100
Time Limit Exceeded

input:

2000
1 0
0 1
2 -1
-1 2
3 -2
-2 3
4 -3
-3 4
5 -4
-4 5
6 -5
-5 6
7 -6
-6 7
8 -7
-7 8
9 -8
-8 9
10 -9
-9 10
11 -10
-10 11
12 -11
-11 12
13 -12
-12 13
14 -13
-13 14
15 -14
-14 15
16 -15
-15 16
17 -16
-16 17
18 -17
-17 18
19 -18
-18 19
20 -19
-19 20
21 -20
-20 21
22 -21
-21 22
23 -22
-22 23
24 -23
-23 24...

output:


result: