QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#576245#3195. Within Arm's ReachSunsetGlow95AC ✓905ms4484kbC++142.1kb2024-09-19 19:36:162024-09-19 19:36:16

Judging History

This is the latest submission verdict.

  • [2024-09-19 19:36:16]
  • Judged
  • Verdict: AC
  • Time: 905ms
  • Memory: 4484kb
  • [2024-09-19 19:36:16]
  • Submitted

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;
}

Details

Tip: Click on the bar to expand more detailed information

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