QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#82231#5355. 多边形上天Recalling_Clouds0 2ms3904kbC++144.2kb2023-02-27 11:35:092023-02-27 11:35:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-27 11:35:11]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:3904kb
  • [2023-02-27 11:35:09]
  • 提交

answer

//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)

#define x first
#define y second
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)

char _c; bool _f; template <class T> inline void IN (T & x) {
	_f = 0, x = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
	while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f == 1) x = -x;
}

template <class T> inline void chkmin (T & x, T y) { if (x < y) x = y; }
template <class T> inline void chkmax (T & x, T y) { if (x < y) x = y; }

const int N = 2e3 + 5;

const double eps = 1e-6;
const double pi = acos ( -1 );
const double g = 9.8;
const double inf = 1e18;

inline bool equal (double a, double b) { return fabs (a - b) < eps; }

double v, w, r, theta;
inline double f1 (double t) { return cos (theta - t * w) * w * r + g * t; }
inline double f2 (double t) { return sin (theta - t * w) * w * r + v; }

inline double calc1 (double L) { return (sin (theta) - sin (theta - L * w)) * r + L * L / 2 * g; } 
inline double calc2 (double L) { return (cos (theta - L * w) - cos (theta)) * r + L * v; }

int n;
pair <double, double> c;

inline double findtp (double L, double R) {
    for (int t = 50; t; -- t) {
        double len = (R - L) / 3, m1 = L + len, m2 = R - len;
        (f1 (m1) < f1 (m2)) ? L = m1 : R = m2;
    }
    return L;
}
inline double doit (int a, int b, double & ret_a) {
    if (! b) return ret_a = a, 0;
        cout << "Yes" << endl ;


    r = sqrt ((c.x - a) * (c.x - a) + (c.y - b) * (c.y - b));
    theta = atan2 (b - c.y, a - c.x);

    double st = theta / w, T = pi / w;
    double tp = findtp (st - T / 2, st + T / 2);
    double shift = (st + T / 2 - tp) * 2;
    swap (tp, st);

    if (st > 0) st -= floor (st / (2 * T)) * 2 * T;
    if (st < 0) st += ceil ( ( - st) / (2 * T)) * 2 * T;

    if (shift < eps) {
        double L = 0, R = 2e5;
        for (int t = 50; t; -- t) {
            double mid = (L + R) / 2;
            calc1 (mid) >= b ? R = mid : L = mid;
        }
        return ret_a = a + calc2 (L), L;
    }

    auto findrt = [&] (double L) -> double {
        double R = L + shift;
        if (f1 (R) >= 0) return inf;

        for (int t = 30; t; -- t) {
            double mid = (L + R) / 2;
            f1 (mid) >= 0 ? L = mid : R = mid;
        }
        return L;
    };

    double lt = findrt (st - 2 * T), ret = 0, tot;
    if (equal (lt, inf)) ret = 0;
    else {
        int L = 0, R = 2e5; // st + mid * 2 * T
        if (lt >= 0) st -= 2 * T;

        while (L <= R) {
            int mid = (L + R) >> 1;
            double lp = findrt (st + 2 * mid * T);
            ! equal (lp, inf) ? tot = mid, ret = lp, L = mid + 1 : R = mid - 1;
        }
    }

    if (calc1 (ret) < b) {
        double L = ret, R = 1e6;
        for (int t = 50; t; -- t) {
            double mid = (L + R) / 2;
            calc1 (mid) >= b ? R = mid : L = mid;
        }
        ret = L;
    } else {
        int L = 0, R = tot, pt = -1;
        double lm;

        while (L <= R) {
            int mid = (L + R) >> 1;
            double lp = findrt (st + 2 * mid * T);

            assert (! equal (lp, inf));
            calc1 (lp) >= b ? lm = lp, pt = mid, R = mid - 1 : L = mid + 1;
        }
        assert ( ~ pt);

        double A = st + 2 * (pt - 1) * T + shift, B = lm;
        for (int t = 50; t; -- t) {
            double mid = (A + B) / 2;
            calc1 (mid) >= b ? B = mid : A = mid;
        }
        ret = A;
    }
    return ret_a = a + calc2 (ret), ret;
}

pair <int, int> p[N];
signed main () {
    // freopen ( "nothing.in", "r", stdin ) ;
    // freopen ( "nothing.out", "w", stdout ) ;

    IN (n), IN (v), IN (w);
    lep (i, 1, n) IN (p[i].x), IN (p[i].y);

    lep (i, 1, n) c.x += p[i].x, c.y += p[i].y;
    c.x /= n, c.y /= n;

    double ans_t = inf, ans_a = 0;
    lep (i, 1, n) {
        double now_a, now_t = doit (p[i].x, p[i].y, now_a);
        if (ans_t > now_t) swap (now_t, ans_t), swap (ans_a, now_a);
    }

    printf ("%.10lf\n", ans_a);
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3904kb

input:

8
53 0
11 935
11 945
1 935
61 915
121 935
111 945
111 935
61 925

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
785.2497877469

result:

wrong output format Expected double, but "Yes" found

Subtask #2:

score: 0
Wrong Answer

Test #43:

score: 0
Wrong Answer
time: 2ms
memory: 3836kb

input:

8
811 14
11 911
11 921
1 911
61 891
121 911
111 921
111 911
61 901

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
10885.3995714496

result:

wrong output format Expected double, but "Yes" found

Subtask #3:

score: 0
Skipped

Dependency #1:

0%