[LOJ 2082] 「JSOI2016」炸弹攻击 2

链接

题解

枚举发射源，将发射源当做原点，对敌人和激光塔极角排序。

由于敌人纵坐标均为正，而其它点均为负，因此每两个角度差在 \(\pi\) 以内的激光塔内部的敌人的个数之和就是该发射源对答案的贡献。

用前缀和以及 \(Two Pointers\) 可以在 \(O(N)\) 的时间内统计一个发射源的贡献。

时间复杂度 \(O(N2LogN)\)。

代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 808

#define ll long long

using namespace std;

int D, S, T, sd[maxn << 2], st[maxn << 2], tmp[maxn << 2];

ll ans;

struct point {

    int x, y;

    inline void get() { scanf("%d%d", &x, &y); }

} d[maxn], s[maxn], t[maxn];

inline point operator-(point a, point b) { return (point){ a.x - b.x, a.y - b.y }; }

inline ll cm(point a, point b) { return 1ll * a.x * b.y - 1ll * a.y * b.x; }

inline bool sign(int x) {

    if (x >= 0)

        return 1;

    return 0;

}

struct data {

    point v;

    bool tp;

} a[maxn << 2];

inline bool cmp(data a, data b) {

    return sign(a.v.y) > sign(b.v.y) || sign(a.v.y) == sign(b.v.y) && (cm(a.v, b.v) < 0);

}

void init() {

    scanf("%d", &D);

    for (int i = 1; i <= D; ++i) d[i].get();

    scanf("%d", &S);

    for (int i = 1; i <= S; ++i) s[i].get();

    scanf("%d", &T);

    for (int i = 1; i <= T; ++i) t[i].get();

}

void solve() {

    ans = 0;

    for (int i = 1; i <= S; ++i) {

        int cnt = 0;

        int xxx = ans;

        for (int j = 1; j <= D; ++j) a[++cnt].v = d[j] - s[i], a[cnt].tp = 0;

        for (int j = 1; j <= T; ++j) a[++cnt].v = t[j] - s[i], a[cnt].tp = 1;

        sort(a + 1, a + cnt + 1, cmp);

        for (int j = 1; j <= cnt; ++j) a[cnt + j] = a[j];

        //

        for (int j = 1; j <= cnt << 1; ++j) {

            sd[j] = sd[j - 1], st[j] = st[j - 1], tmp[j] = tmp[j - 1];

            if (a[j].tp)

                ++st[j], tmp[j] += sd[j];

            else

                ++sd[j];

        }

        for (int j = 1, k = 1; j <= cnt; ++j)

            if (a[j].tp) {

                k = max(k, j);

                while ((k < (cnt << 1)) &&

                       (cm(a[j].v, a[k + 1].v) < 0))

                    ++k;

                ans += tmp[k] - tmp[j] -

                       1ll * (st[k] - st[j]) * sd[j];

            }

    }

    printf("%lld\n", ans);

}

int main() {  // freopen("1.in","r",stdin);

    init();

    solve();

    return 0;

}

巴特西

[LOJ 2082] 「JSOI2016」炸弹攻击 2

[LOJ 2082] 「JSOI2016」炸弹攻击 2

链接

题解

代码

最新文章

热门文章