QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#576245 | #3195. Within Arm's Reach | SunsetGlow95 | AC ✓ | 905ms | 4484kb | C++14 | 2.1kb | 2024-09-19 19:36:16 | 2024-09-19 19:36:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MXN = 25;
const double T = 100;
const double EPS = 1e-13;
const double RATE = 0.99;
const double PI = acos(-1);
int N, len[MXN], tx, ty;
double tlen, angle[MXN], ans[MXN], dans[MXN], dlen;
inline double cald(double x, double y) {
return sqrt(x * x + y * y);
}
inline pair<double, double> conv(double l, double theta) {
return make_pair(l * cos(theta), l * sin(theta));
}
inline double random(mt19937& rnd) {
return rnd() * 2.0 / UINT32_MAX - 1;
}
pair<double, double> calc(bool output_mode = false) {
double x(0), y(0), a(0);
for (int i(0); i != N; ++i) {
a = angle[i];
pair<double, double> vec(conv(len[i], a));
x += vec.first, y += vec.second;
if (output_mode)
cout << setprecision(6) << fixed << x
<< ' ' << setprecision(6) << fixed << y << endl;
}
return make_pair(x, y);
}
int main() {
cin >> N;
for (int i(0); i != N; ++i) cin >> len[i];
cin >> tx >> ty;
tlen = cald(tx, ty);
mt19937 rnd((random_device())());
double dlen(cald(calc().first, calc().second));
while (clock() * 1.0 / CLOCKS_PER_SEC < 0.9) {
pair<double, double> vec(calc());
double nlen(cald(vec.first, vec.second));
for (double temp(T); temp > EPS; temp *= RATE) {
for (int i(1); i != N; ++i)
angle[i] = ans[i] + random(rnd) * temp / 100 * 2 * PI;
vec = calc();
double clen(cald(vec.first, vec.second));
if (abs(clen - tlen) < abs(nlen - tlen) ||
rnd() < exp((abs(nlen - tlen) - abs(clen - tlen)) * 10000 / temp)) {
for (int i(0); i != N; ++i) ans[i] = angle[i];
nlen = clen;
}
if (abs(clen - tlen) < abs(dlen - tlen)) {
for (int i(0); i != N; ++i) dans[i] = angle[i];
dlen = clen;
}
}
}
for (int i(0); i != N; ++i) angle[i] = dans[i];
pair<double, double> cur(calc());
if (tlen) angle[0] = atan2(ty, tx) - atan2(cur.second, cur.first);
else angle[0] = 0;
for (int i(1); i != N; ++i) angle[i] += angle[0];
calc(1);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 901ms
memory: 4388kb
input:
2 4 2 -8 -3
output:
-3.745317 -1.404494 -5.617975 -2.106741
result:
ok ACCEPTED
Test #2:
score: 0
Accepted
time: 896ms
memory: 3984kb
input:
1 10 10 0
output:
10.000000 0.000000
result:
ok ACCEPTED
Test #3:
score: 0
Accepted
time: 896ms
memory: 4108kb
input:
1 10 0 0
output:
10.000000 0.000000
result:
ok ACCEPTED
Test #4:
score: 0
Accepted
time: 896ms
memory: 4480kb
input:
2 10 5 2 2
output:
7.071068 7.071068 3.535534 3.535534
result:
ok ACCEPTED
Test #5:
score: 0
Accepted
time: 896ms
memory: 4300kb
input:
3 100 20 20 80 90
output:
59.894804 80.078789 77.276911 70.186248 80.000000 90.000000
result:
ok ACCEPTED
Test #6:
score: 0
Accepted
time: 896ms
memory: 4412kb
input:
3 5 10 4 5 3
output:
-4.490013 2.199951 4.314743 6.940866 5.000000 3.000000
result:
ok ACCEPTED
Test #7:
score: 0
Accepted
time: 904ms
memory: 4416kb
input:
3 3 3 3 -1 -1
output:
-2.683493 1.341218 -3.977680 -1.365270 -1.000000 -1.000000
result:
ok ACCEPTED
Test #8:
score: 0
Accepted
time: 901ms
memory: 4428kb
input:
11 31 1 62 125 250 500 2 7 3 1000 15 -2 -3
output:
17.196384 25.793107 17.750617 26.625469 52.141983 78.212618 121.479391 182.218982 260.154466 390.231539 537.504671 806.256614 538.614045 807.920732 542.496861 813.745142 544.160965 816.241290 -10.539346 -15.808928 -2.218801 -3.328201
result:
ok ACCEPTED
Test #9:
score: 0
Accepted
time: 903ms
memory: 4308kb
input:
3 5 3 4 5 3
output:
4.849579 1.217204 1.964399 0.395173 5.000000 3.000000
result:
ok ACCEPTED
Test #10:
score: 0
Accepted
time: 905ms
memory: 4476kb
input:
20 3 9 15 5 7 13 4 17 8 999 16 6 10 14 2 12 1000 11 998 1 234 -123
output:
-2.941755 -0.588284 -2.150656 8.376880 -16.124269 13.830149 -20.803651 12.068509 -27.803414 12.010913 -30.326875 -0.741818 -26.787794 1.122293 -10.381138 -3.329855 -15.179321 -9.731218 879.274668 435.187945 863.654852 431.720765 869.654679 431.675157 862.953817 439.097990 848.954590 439.245119 847.6...
result:
ok ACCEPTED
Test #11:
score: 0
Accepted
time: 903ms
memory: 4424kb
input:
20 11 857 509 877 13 811 991 997 937 853 787 739 919 7 859 941 929 773 947 863 9871 -7919
output:
9.177085 -6.064743 863.344923 -75.680147 1369.230661 -19.460751 1764.406534 -802.381583 1775.941299 -808.377348 2586.717850 -789.340988 3521.896874 -1117.245234 3813.813988 -2070.551795 4742.997492 -1949.775074 5525.996308 -2288.185850 5475.883566 -3073.588749 6214.161765 -3106.242999 6821.958307 -3...
result:
ok ACCEPTED
Test #12:
score: 0
Accepted
time: 904ms
memory: 4164kb
input:
20 919 625 820 609 760 41 101 232 545 812 234 177 678 131 359 444 519 77 173 917 0 0
output:
919.000000 0.000000 294.156046 13.965407 -469.528733 -284.674106 -303.162142 301.161329 395.325044 1.635618 411.697679 -35.953433 495.997046 19.675846 272.062263 80.315873 -25.183706 537.119806 -751.275268 173.615964 -758.287803 -60.278936 -880.765420 67.503039 -733.056874 -594.211541 -676.050430 -4...
result:
ok ACCEPTED
Test #13:
score: 0
Accepted
time: 904ms
memory: 4484kb
input:
20 919 625 820 609 760 41 101 232 545 812 234 177 678 131 359 444 519 77 173 917 0 -20000
output:
0.000015 -919.000000 0.000014 -1544.000000 0.000011 -2364.000000 0.000013 -2973.000000 0.000008 -3733.000000 0.000008 -3774.000000 0.000007 -3875.000000 0.000014 -4107.000000 0.000004 -4652.000000 -0.000005 -5464.000000 -0.000006 -5698.000000 -0.000006 -5875.000000 -0.000017 -6553.000000 -0.000015 -...
result:
ok ACCEPTED
Test #14:
score: 0
Accepted
time: 903ms
memory: 4340kb
input:
20 408 663 148 685 731 606 538 289 850 577 732 34 656 200 325 901 105 575 754 910 -2498 1075
output:
-128.902588 -387.102212 -782.091779 -500.737075 -841.632711 -365.242140 -627.896567 -1016.043078 -374.149083 -330.497154 37.600524 114.135572 -310.235715 524.566993 -44.352063 637.822826 805.257360 663.587705 338.012969 325.044238 313.353488 1056.628758 311.790827 1090.592829 -244.423337 1438.388462...
result:
ok ACCEPTED
Test #15:
score: 0
Accepted
time: 904ms
memory: 4324kb
input:
20 440 377 296 985 425 377 777 533 710 620 975 854 312 130 13 900 745 416 550 507 -1080 -2184
output:
-108.880541 -426.315643 224.714102 -250.692144 -42.922864 -377.129694 -935.963633 -792.705421 -1324.895220 -964.044911 -1611.231791 -718.809579 -1533.164402 -1491.877806 -1379.024969 -2002.103281 -932.649060 -1449.972365 -1534.308074 -1599.660145 -1975.516919 -2469.119606 -1203.660675 -2103.669284 -...
result:
ok ACCEPTED
Test #16:
score: 0
Accepted
time: 903ms
memory: 4412kb
input:
4 890 306 65 120 -10 14
output:
-517.301999 724.222785 -339.443107 475.220346 -301.662623 422.327671 -231.914039 324.679655
result:
ok ACCEPTED
Test #17:
score: 0
Accepted
time: 905ms
memory: 4340kb
input:
20 149 380 248 401 43 631 977 207 511 496 14 425 179 867 9 801 432 766 684 358 -3887 7982
output:
-65.234835 133.960503 -231.605562 475.604735 -340.184344 698.572553 -515.749232 1059.097130 -534.575394 1097.756871 -810.838364 1665.066109 -1238.586257 2543.451412 -1329.214526 2729.557610 -1552.939362 3188.979200 -1770.096940 3634.914830 -1776.226387 3647.501723 -1962.298906 4029.603827 -2040.6682...
result:
ok ACCEPTED
Test #18:
score: 0
Accepted
time: 903ms
memory: 4348kb
input:
20 121 803 712 959 971 452 892 694 465 489 201 20 757 995 643 853 797 755 203 452 2501 643
output:
-43.906869 112.752769 693.160312 -205.902171 1273.773642 206.204806 2133.721823 630.669323 1165.165773 561.820375 1428.187937 929.411643 2272.436222 641.472701 2261.371528 1335.384492 1900.477078 1042.160694 1414.645511 986.584725 1271.223306 1127.407561 1269.874405 1107.453102 560.826726 842.310898...
result:
ok ACCEPTED
Test #19:
score: 0
Accepted
time: 904ms
memory: 4324kb
input:
20 397 740 397 939 260 942 166 856 939 700 98 740 470 621 506 843 433 261 951 662 10019 -4091
output:
343.332471 -199.328408 991.617970 -556.155973 1379.084199 -469.675213 2286.202147 -712.281949 2496.746148 -864.831034 3278.254514 -1390.767033 3431.117822 -1455.488042 4247.413271 -1713.165631 4809.974269 -2464.994151 5322.456522 -2941.819004 5407.389827 -2892.927964 6146.013650 -2938.037251 5935.54...
result:
ok ACCEPTED
Test #20:
score: 0
Accepted
time: 900ms
memory: 4400kb
input:
6 870 915 808 598 10 881 -4251 -946
output:
-849.226302 -188.983302 -1742.378100 -387.741611 -2531.084821 -563.257159 -3114.805885 -693.156044 -3124.567106 -695.328266 -3984.530748 -886.701032
result:
ok ACCEPTED
Test #21:
score: 0
Accepted
time: 900ms
memory: 4348kb
input:
1 500 -40 80
output:
-223.606798 447.213595
result:
ok ACCEPTED