結果

問題 No.620 ぐるぐるぐるりん
ユーザー pekempeypekempey
提出日時 2017-12-20 18:14:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,784 bytes
コンパイル時間 964 ms
コンパイル使用メモリ 88,820 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-12-16 07:07:46
合計ジャッジ時間 7,956 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,496 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 4 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 WA -
testcase_11 AC 2 ms
5,248 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 21 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 TLE -
testcase_29 AC 21 ms
5,248 KB
testcase_30 AC 21 ms
8,960 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>

using namespace std;

const double pi = acos(-1);
mt19937 mt(123456);

int t;
long double p, w, v, gx, gy;

long double hypot2(long double x, long double y) {
  return x*x + y*y;
}

bool solve2() {
  long double gr = hypot(gx, gy);
  long double mn = 1e100;

  long double x = v+1;
  long double y = w;

  long double det = (1+v)*(1+v) + w*w;

  long double gx = ::gx;
  long double gy = ::gy;

  if (t >= 2 && hypot2(x, y) + hypot2(gx, gy) < p - 0.00001) {
    cerr << "type1" << endl;
    printf("%.30Lf %.30Lf\n", -x, -y);
    for (int j = 0; j < t - 2; j++) {
      printf("%.30Lf %.30Lf\n", 0.0L, 0.0L);
    }
    printf("%.30Lf %.30Lf\n", gx, gy);
    return true;
  }


  for (int i = 0; i < t - 1; i++) {
    long double gx0 = gx;
    long double gy0 = gy;

    gx = gx0*(v+1) + gy0*w;
    gy = gy0*(v+1) - gx0*w;
    gx /= det;
    gy /= det;

    long double dist = hypot(gx, gy);

    long double score = dist*dist + x*x + y*y;
    if (score < p - 0.00001) {
      cerr << "type2" << endl;
      printf("%.30Lf %.30Lf\n", -x, -y);
      for (int j = 0; j < t - 3 - i; j++) {
        printf("%.30Lf %.30Lf\n", 0.0L, 0.0L);
      }
      printf("%.30Lf %.30Lf\n", gx, gy);
      printf("%.30Lf %.30Lf\n", 0.0L, 0.0L);
      return true;
    }
  }

  return false;
}

bool solve() {
  long double gr = hypot(gx, gy);
  long double mn = 1e100;

  for (int ii = 0; ii < 5000; ii++) {
    long double x = 1;
    long double y = 0;

    vector<long double> vx(t);
    vector<long double> vy(t);

    long double theta = uniform_real_distribution<long double>(0, 2*pi)(mt);
    long double c = uniform_real_distribution<long double>(1e-6, 10)(mt);
    vx[0] = cos(theta) - 1;
    vy[0] = sin(theta);

    for (int i = 0; i < t; i++) {
      long double x0 = x;
      long double y0 = y;

      x = x0 - y0*w + x0*v + vx[i];
      y = y0 + x0*w + y0*v + vy[i];

      long double r = hypot(x, y);
      long double tr;

      tr = gr*pow((long double)i / t, c);
      long double d = tr - r;

      vx[i] += d*x / r;
      vy[i] += d*y / r;

      x += d*x / r;
      y += d*y / r;
    }

    vx[t - 1] += gx - x;
    vy[t - 1] += gy - y;

    long double s = 0;
    for (int i = 0; i < t; i++) {
      s += vx[i]*vx[i] + vy[i]*vy[i];
    }
    mn = min(mn, s);

    if (s < p - 0.001) {
      cerr << "type3" << endl;
      for (int i = 0; i < t; i++) {
        printf("%.16Lf %.16Lf\n", vx[i], vy[i]);
      }

      fprintf(stderr, "Sum: %.30Lf\n", s);
      fprintf(stderr, "p:   %.30Lf\n", p);

      return true;
    }
  }
  return false;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> t >> p >> w >> v >> gx >> gy;
    if (!solve2()) {
      solve();
    }
  }
}
0