QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515499 | #2268. Solar Car | IllusionaryDominance | WA | 1ms | 6352kb | C++20 | 3.3kb | 2024-08-11 18:05:39 | 2024-08-11 18:05:39 |
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) {
// 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'