QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113227#1950. Surveillanceckiseki#WA 1ms3704kbC++143.2kb2023-06-16 18:33:402023-06-16 18:34:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-16 18:34:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3704kb
  • [2023-06-16 18:33:40]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
using std::cerr;
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif

#define all(v) begin(v),end(v)

using namespace std;

using P = complex<int>;

using llf = long double;

int cross(P a, P b) {
    return imag(conj(a) * b);
}

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n;
    cin >> n;
    vector<P> p(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        p[i] = {x, y};
    }

    {
        vector<int> colinear(n);
        for (int i = 0; i < n; i++) {
            int C =
                cross(p[(i + 2) % n] - p[(i + 1) % n],
                        p[(i + 1) % n] - p[(i + 0) % n]);
            if (C == 0) {
                colinear[ (i + 1) % n ] = true;
            }
        }
        vector<P> q;
        for (int i = 0; i < n; i++)
            if (!colinear[i])
                q.emplace_back(p[i]);
        p = q;
    }

    int pos = -1;
    for (int i = 0; i < n; i++) {
        int C =
            cross(
                    p[(i + 1) % n] - p[(i + 0) % n],
                    p[(i + 2) % n] - p[(i + 1) % n]
                    );
        if (C < 0) {
            pos = (i + 1) % n;
        }
    }

    if (pos == -1) {
        int area = cross(p[1] - p[0], p[2] - p[1]);
        cout << area << '\n';
        return 0;
    }

    assert (p.size() == 6);
    n = 6;

    rotate(p.begin(), p.begin() + pos, p.end());

    for (int i = 0; i < n; i++) {
        if (i != 3)
            p[i] -= p[3];
    }
    p[3] = {0, 0};

    int tot_area = 0;
    for (int i = 1; i + 1 < n; i++) {
        tot_area += cross(p[i] - p[0], p[i + 1] - p[0]);
    }
    tot_area /= 2;

    debug(tot_area);

    // x^2 + (sB/t) * y >= s^2 + sB

    llf ans = tot_area;

    const auto gao = [](auto p) {
        int s = real(p[0]), t = imag(p[0]);
        int B = real(p[5]) - s;


        int h = imag(p[2]);

        debug(s, t, B, h);

        {
            llf jiao = s * s + s * B - s * B * h / llf(t);
            if (jiao >= 0) {
                jiao = sqrt(jiao);
                // jiao ~ s  h + (x^2 - s^2 - sB) / (sB/t)

            } else {
                jiao = 0;
                // 0 ~ s  h + (x^2 - s^2 - sB) / (sB/t)
            }

            llf C = h - (s * s + s * B) / ((s * B) / llf(t));
            llf integ = -(jiao*jiao*jiao - s*s*s) / 3 * t / (s*B)
                + C * (s - jiao);
            debug(integ);
            return integ;
        }
    };

    ans -= gao(p);
    debug(ans);

    reverse(p.begin() + 1, p.end());
    for (auto &pi: p)
        pi = { imag(pi), real(pi) };

    ans -= gao(p);

    cout << fixed << setprecision(20);
    cout << ans << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3508kb

input:

4
-5 6
-5 -2
10 -2
10 6

output:

120

result:

ok found '120.0000000', expected '120.0000000', error '0.0000000'

Test #2:

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

input:

6
627 -788
444 -788
444 -986
-102 -986
-102 -993
627 -993

output:

-nan

result:

wrong output format Expected double, but "-nan" found