QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708195#3854. Radarahsoltan#WA 4ms3952kbC++202.2kb2024-11-03 20:12:142024-11-03 20:12:14

Judging History

你现在查看的是最新测评结果

  • [2024-11-03 20:12:14]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3952kb
  • [2024-11-03 20:12:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}";
}
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")";
}
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif

using ld = long double;

using pp = pair<ll, ll>;

ll sgn(ll x) {
  if(!x)
    return 0;
  if(x < 0)
    return -1;
  return 1;
}

ll cross(pp a, pp b) {
  return a.first * b.second - a.second * b.first;
}

bool cmp(pp a, pp b) {
  auto half = [](pp p) {return sgn(p.second) ?: -sgn(p.first);};
  int A = half(a), B = half(b);
  return A == B ? cross(a, b) > 0 : A < B;
}

using db = long double;

int main() {

  cin.tie(0)->sync_with_stdio(0);

  int r, a, n;
  cin >> r >> a >> n;
  vector<ll> di(r);
  vector<ll> odi(r);
  vector<pair<ll, ll>> an(a);
  rep(i, 0, r) {
    cin >> di[i];
    odi[i] = di[i];
    di[i] *= di[i];
  }
  for(auto &[i, j] : an)
    cin >> i >> j;

  sort(all(di));
  sort(all(an), cmp);

  debug(an);
  debug(di);

  cout << setprecision(10) << fixed;
  
  rep(_, 0, n) {
    pp p;
    cin >> p.first >> p.second;
    ll d = p.first * p.first + p.second * p.second;
    auto it0 = lower_bound(all(di), d);
    int p0 = it0 - di.begin();

    auto it1 = lower_bound(all(an), p, cmp);
    int p1 = it1 - an.begin();

    complex<db> moj(db(p.first), db(p.second));

    db mn = 1e18;

    for(int d0 = -1; d0 <= 1; d0++) {
      for(int d1 = -1; d1 <= 1; d1++) {
        int i = ((p0 + d0) % r + r) % r;
        int j = ((p1 + d1) % a + a) % a;
        complex<db> kan(db(an[j].first), db(an[j].second));
        kan /= abs(kan);
        kan *= odi[i];
        mn = min(mn, abs(kan - moj));
      }
    }

    cout << mn << endl;
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3916kb

input:

3 8 4
2
4
7
1 0
2 1
0 1
-1 1
-5 -2
-5 -6
-2 -7
6 -1
-1 -1
3 1
-5 -3
8 1

output:

0.6052910729
0.9777722905
1.5518451054
1.4142135624

result:

ok 4 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

1 8 32
7
0 1
1 0
0 -1
-1 0
1 -1
-1 1
-1 -1
1 1
20 10
10 20
-20 10
10 -20
-10 20
20 -10
-10 -20
-20 -10
2 1
1 2
-2 1
1 -2
-1 2
2 -1
-1 -2
-2 -1
5 0
0 5
-5 0
0 -5
5 5
5 -5
-5 5
-5 -5
9 0
0 9
-9 0
0 -9
9 9
9 -9
-9 9
-9 -9

output:

15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
15.8749850993
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
4.9296567010
2.0000000000
2.0000000000
2.0000000000
2.0000000000
0.0710678119
0.0710678119
0.0710...

result:

ok 32 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 3880kb

input:

3 4 1681
16
8
4
-1 0
0 -1
0 1
1 0
-9 17
-4 -7
2 -13
-11 -17
15 -19
-7 1
-8 14
-8 -7
-8 20
-16 -3
12 14
-3 12
9 -5
-18 11
3 -1
2 0
-18 0
0 -19
-1 -19
18 -8
2 20
5 -8
-8 -19
-9 -16
20 -19
14 -1
3 10
-1 -4
4 10
16 17
19 -7
-17 4
1 -12
-5 -12
-5 -10
-15 -5
-10 -19
-2 -10
-4 -16
-2 4
-14 8
-17 16
4 1
16 ...

output:

9.0553851381
4.1231056256
3.6055512755
11.0453610172
15.2970585408
1.4142135624
8.2462112512
7.0000000000
8.9442719100
3.0000000000
12.1655250606
5.0000000000
5.0990195136
11.1803398875
1.4142135624
2.0000000000
2.0000000000
3.0000000000
3.1622776602
8.2462112512
4.4721359550
5.0000000000
8.54400374...

result:

ok 1681 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

3 4 1681
16
8
4
-1 -1
1 -1
-1 1
1 1
17 1
13 7
-13 -18
-1 18
4 -12
-9 3
5 10
-10 1
-12 -4
14 10
-18 19
0 -3
-7 3
-16 11
-15 9
16 1
-8 -12
3 1
0 -2
15 -18
-14 20
9 -19
17 12
20 5
-3 -6
12 -1
9 10
-13 -9
-20 -15
-11 6
17 -2
-10 -19
15 -8
-6 17
18 15
2 -3
18 -12
8 -3
-11 -6
19 -15
20 0
3 4
2 -16
-6 -17
...

output:

11.7773721193
4.6315936826
6.8956561010
12.2914229054
6.5559640036
4.2703042060
4.3925360004
6.3678258857
6.5559640036
2.9903163794
10.1875203595
2.8336261665
2.9770648314
4.6967798602
4.3522398887
11.3284558098
3.3840301477
1.8364593657
2.9472515164
7.6351318958
9.0921846698
8.0269747761
5.72755681...

result:

ok 1681 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

1 4 16
7
0 1
1 0
0 -1
-1 0
3 0
0 3
-3 0
0 -3
3 3
3 -3
-3 3
-3 -3
8 0
0 8
-8 0
0 -8
8 8
8 -8
-8 8
-8 -8

output:

4.0000000000
4.0000000000
4.0000000000
4.0000000000
5.0000000000
5.0000000000
5.0000000000
5.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000
8.0622577483
8.0622577483
8.0622577483
8.0622577483

result:

ok 16 numbers

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3864kb

input:

30 4 120
128
1
2
256
4
512
1024
2048
8
4096
32768
131072
262144
524288
8192
268167
16
536334
16384
1047
32
2095
8380
64
134083
65536
4190
67041
33520
16760
536334 0
-536335 0
0 536334
0 -536335
-1 1
-2 2
-4 4
-8 8
-16 16
-32 32
-64 64
-128 128
-256 256
-512 512
-1024 1024
-2048 2048
-4096 4096
-8192...

output:

1.0000000000
2.0000000000
4.0000000000
8.9442719100
20.0000000000
481.0654841079
85.0411665019
175.4536975957
356.4267105591
3620.3867196751
130052.0314335766
6476.3446480248
5781.3161131355
10870.1374876310
21739.6176829309
40847.4768865838
65536.0000000000
145876.1054628207
326779.2180433144
72970...

result:

wrong answer 4th numbers differ - expected: '8.0000000', found: '8.9442719', error = '0.1180340'