QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515469#2268. Solar CarIllusionaryDominance#WA 1ms4240kbC++203.3kb2024-08-11 17:57:002024-08-11 17:57:01

Judging History

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

  • [2024-08-11 17:57:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4240kb
  • [2024-08-11 17:57:00]
  • 提交

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

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

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

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:

2981.8881456571
3141.3464678157
2981.8881456571
2879.7889292056
3288.1857950114
3488.1571065535
2857.5698945898
1863.0238860519
2416.1465183730
1863.0238860519
2773.4833810999
2969.2691506942
2981.8881456571
2981.8881456571
2773.4833810999
2735.0631626903
2416.1465183730
2899.6131513348
2879.7889292...

result:

wrong answer 1st numbers differ - expected: '3288.1857950', found: '2981.8881457', error = '0.0931510'