QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515469 | #2268. Solar Car | IllusionaryDominance# | WA | 1ms | 4240kb | C++20 | 3.3kb | 2024-08-11 17:57:00 | 2024-08-11 17:57:01 |
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 < 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'