QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515665 | #2268. Solar Car | IllusionaryDominance | TL | 1ms | 6452kb | C++20 | 3.2kb | 2024-08-11 20:18:53 | 2024-08-11 20:18:54 |
Judging History
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
*/
Details
Tip: Click on the bar to expand more detailed information
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...