QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728257#9576. Ordainer of Inexorable Judgmentucup-team087#WA 1ms4104kbC++144.8kb2024-11-09 14:51:272024-11-09 14:51:31

Judging History

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

  • [2024-12-23 14:23:26]
  • hack成功,自动添加数据
  • (/hack/1303)
  • [2024-12-06 11:32:56]
  • hack成功,自动添加数据
  • (/hack/1271)
  • [2024-11-14 21:58:28]
  • hack成功,自动添加数据
  • (/hack/1181)
  • [2024-11-09 14:51:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4104kb
  • [2024-11-09 14:51:27]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


using Double = long double;
const Double EPS = 1e-10L;
const Double INF = 1e+10L;
const Double PI = acos(-1.0L);
inline int sig(Double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
inline Double sq(Double r) { return r * r; }

struct Pt {
  Double x, y;
  Pt() {}
  Pt(Double x_, Double y_) : x(x_), y(y_) {}
  Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
  Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
  Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
  Pt operator/(const Pt &a) const { const Double d2 = a.abs2(); return Pt((x * a.x + y * a.y) / d2, (y * a.x - x * a.y) / d2); }
  Pt operator+() const { return Pt(+x, +y); }
  Pt operator-() const { return Pt(-x, -y); }
  Pt operator*(const Double &k) const { return Pt(x * k, y * k); }
  Pt operator/(const Double &k) const { return Pt(x / k, y / k); }
  friend Pt operator*(const Double &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
  Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
  Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
  Pt &operator*=(const Pt &a) { return *this = *this * a; }
  Pt &operator/=(const Pt &a) { return *this = *this / a; }
  Pt &operator*=(const Double &k) { x *= k; y *= k; return *this; }
  Pt &operator/=(const Double &k) { x /= k; y /= k; return *this; }
  Double abs() const { return sqrt(x * x + y * y); }
  Double abs2() const { return x * x + y * y; }
  Double arg() const { return atan2(y, x); }
  Double dot(const Pt &a) const { return x * a.x + y * a.y; }
  Double det(const Pt &a) const { return x * a.y - y * a.x; }
  friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
  bool operator<(const Pt &a) const { return (x != a.x) ? (x < a.x) : (y < a.y); }
};
inline Double tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }


int N;
Pt A;
Double D, T;
vector<Pt> P;

Double solve(vector<pair<Double, int>> &es) {
  sort(es.begin(), es.end());
  const int esLen = es.size();
// cerr<<es<<endl;
  int now = 0;
  Double ret = 0.0L;
  for (int i = 0; i < esLen - 1; ++i) {
    now += es[i].second;
    if (now) {
      ret += (es[i + 1].first - es[i].first);
    }
  }
  return ret;
}

int main() {
  for (; ~scanf("%d%Lf%Lf%Lf%Lf", &N, &A.x, &A.y, &D, &T); ) {
    P.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%Lf%Lf", &P[i].x, &P[i].y);
    }
    
    const Double R = fmod(T, 2*PI);
    const Double Q = (T - R) / (2*PI);
    
    vector<Double> ps(N), ws(N);
    for (int i = 0; i < N; ++i) {
      ps[i] = P[i].arg();
      ws[i] = asin(min(D / P[i].abs(), 1.0L));
    }
    
    const Double a = A.arg();
    vector<pair<Double, int>> es, fs;
    for (int i = 0; i < N; ++i) {
      const int j = (i + 1) % N;
      Double l0, r0;
      if (sig(P[i].det(P[j])) > 0) {
        l0 = ps[i] - ws[i];
        r0 = ps[j] + ws[j];
      } else {
        l0 = ps[j] - ws[j];
        r0 = ps[i] + ws[i];
      }
      for (int s = -3; s <= +3; ++s) {
        Double l = max(l0 - (a + 2*PI * s), 0.0L);
        Double r = min(r0 - (a + 2*PI * s), 2*PI);
        if (l <= r) {
          es.emplace_back(l, +1);
          es.emplace_back(r, -1);
          chmin(r, R);
          if (l <= r) {
            fs.emplace_back(l, +1);
            fs.emplace_back(r, -1);
          }
        }
      }
    }
    
    Double ans = 0.0L;
    ans += Q * solve(es);
    ans += solve(fs);
    printf("%.12Lf\n", ans);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

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

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.570796326795

result:

ok found '1.5707963', expected '1.5707963', error '0.0000000'

Test #3:

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

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.707752257475

result:

ok found '2500.7077523', expected '2500.7077523', error '0.0000000'

Test #4:

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

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.384241300290

result:

ok found '0.3842413', expected '0.3842413', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4104kb

input:

3 -10000 -10000 10000 10000
-10000 -9999
-10000 -10000
-9999 -10000

output:

2500.240670009608

result:

ok found '2500.2406700', expected '2500.2406700', error '0.0000000'

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 3880kb

input:

4 1 0 1 10000
-2 3400
-4 10000
-4 -10000
-2 -3400

output:

1.853629090307

result:

wrong answer 1st numbers differ - expected: '4999.2191154', found: '1.8536291', error = '0.9996292'