QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515499#2268. Solar CarIllusionaryDominanceWA 1ms6352kbC++203.3kb2024-08-11 18:05:392024-08-11 18:05:39

Judging History

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

  • [2024-08-11 18:05:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6352kb
  • [2024-08-11 18:05:39]
  • 提交

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) {
    // k is left of ij
    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 ++) {
        // fprintf(stderr, "i = %d, x = %d, y = %d, angle = %.3lf\n", i, node[i].x, node[i].y, node[i].angle);
    }
    for (int i = 1; i <= N; i ++) {
        // counter-clockwise
        fprintf(stderr, "i = %d\n", i);
        for (int j = (i < N ? i + 1 : 1), k = -1; j != i && check_pi(node[j].angle, node[i].angle); j = (j < N ? j + 1 : 1)) {
            if (k == -1 || leftOf(i, j, k)) k = j;
            dis[node[i].id][node[j].id] = calc_dis(i, k) + calc_dis(k, j);
            // fprintf(stderr, "i = %d, j = %d, k = %d, id = (%d, %d), res = %.3lf\n", i, j, k, node[i].id, node[j].id, dis[node[i].id][node[j].id]);
        }
        // clockwise
        for (int j = (i > 1 ? i - 1 : N), k = -1; j != i && check_pi(node[j].angle, node[i].angle - Pi); j = (j > 1 ? j - 1 : N)) {
            if (k == -1 || !leftOf(i, j, k)) k = j;
            dis[node[i].id][node[j].id] = calc_dis(i, k) + calc_dis(k, j);
            // fprintf(stderr, "i = %d, j = %d, k = %d, id = (%d, %d), res = %.3lf\n", i, j, k, node[i].id, node[j].id, dis[node[i].id][node[j].id]);
        }
    }
    for (int i = 1; i <= N; i ++) {
        for (int j = i; j <= N; j ++) {
            // fprintf(stderr, "i = %d, j = %d, dis = %.3lf\n", i, j, dis[i][j]);
            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
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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: 1ms
memory: 4172kb

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: 1ms
memory: 4304kb

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

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: -100
Wrong Answer
time: 1ms
memory: 4224kb

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:

2959.7330911236
3392.9648031752
2951.6868569055
3585.4744588962
2551.1454455631
3147.8804664993
3135.1779983020
3696.6349059395
3170.1395208897
3066.6584904931
3629.7731771689
3156.5910206862
3130.9206169846
2966.4495799999
2859.2267240910
2968.1700609774
3123.9322033162
2820.7930981401
3138.8063994...

result:

wrong answer 1st numbers differ - expected: '2964.9150026', found: '2959.7330911', error = '0.0017477'