Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「ZJOI2008」杀蚂蚁 - 模拟 + 几何

题面见杀蚂蚁的可读版本

链接

BZOJ 1033
COGS 2048

题解

根据题意模拟即可 ……

唯一的难点是判断线段和圆的交点。先过圆心做线段的垂线,判断与线段是否有交点,如果有,则设点到线段距离为 a a ,圆心与线段端点距离的较大值为 b b ;否则设圆心与线段距离较小值为 a a ,较大值为 b b

满足

{arb>r \begin{cases} a \leq r \\ b \gt r \end{cases}

即可

保存直线的时候可以用斜截式,但注意斜率不存在和斜率为零的特判。

还有就是不要写错变量名 ……

代码

#include <cstdio>
#include <cmath>
#include <list>
#include <algorithm>

typedef long double real;

const int MAXN = 8;
const int MAXM = 8;
const int MAXS = 20;
const int MAXT = 200000;
const real EPS = 1e-6;

int n, m, s, d, r, t, time;

struct Map {
    int message;
    bool reachable;

    Map() : message(0), reachable(true) {}
} map[MAXN + 1][MAXM + 1];

template <typename T>
struct Point {
    T x, y;

    Point(const T x = 0, const T y = 0) : x(x), y(y) {}

    Map *operator->() const { return &map[static_cast<int>(x)][static_cast<int>(y)]; }

    Point offset(const int id) const {
        switch (id) {
            case 0: return Point(x, y + 1);
            case 1: return Point(x + 1, y);
            case 2: return Point(x, y - 1);
            case 3: return Point(x - 1, y);
            default: return *this;
        }
    }

    bool valid() const { return x >= 0 && x <= n && y >= 0 && y <= m; }

    bool operator==(const Point &p) const { return x == p.x && y == p.y; }
};

inline bool dcmp(const real a) { return fabs(a) <= EPS; }
inline bool dcmp(const real a, const real b) { return dcmp(a - b); }

inline bool isnan(const real x) { return x != x; }
inline bool isinf(const real x) { return !isnan(x) && isnan(x - x); }

template <typename T> inline T sqr(const T &x) { return x * x; }

template <typename Ta, typename Tb>
inline real distance(const Point<Ta> a, const Point<Tb> b) {
    return sqrt(static_cast<real>(sqr(a.x - b.x) + sqr(a.y - b.y)));
}

struct Ant {
    Point<int> position, lastPosition;
    int level;
    int hpLimit, hp;
    bool hasCake;
    int spawnTime;

    Ant(const int level) : position(0, 0), lastPosition(-1, -1), level(level), hpLimit(floor(4 * pow(1.1, level))), hp(hpLimit), hasCake(false), spawnTime(time) {
        // printf("spawn Ant(%d)\n", level);
        position->reachable = false;
    }

    inline void moveTo(const Point<int> &nextPosition) {
        lastPosition = position;
        position = nextPosition;
        if (lastPosition == position) return;
        // printf("moveTo(): from [%d, %d] to [%d, %d]\n", lastPosition.x, lastPosition.y, position.x, position.y);
        lastPosition->reachable = true;
        position->reachable = false;
    }

    inline int age() const {
        return time - spawnTime;
    }

    inline bool attackable(const Point<int> &p) {
        const real dist = distance(position, p);
        return dist < r || dcmp(dist, r);
    }
};

struct Line {
    real k, b;

    /*
     * k != nan: y = kx + b
     * k == nan: x = b
     */

    Line(const Point<int> &p1, const Point<int> &p2) {
        const real x1 = p1.x, y1 = p1.y, x2 = p2.x, y2 = p2.y;
        if (x1 == x2) {
            k = NAN;
            b = x1;
        } else {
            k = (y2 - y1) / (x2 - x1);
            b = y1 - k * x1;
        }
    }

    Line(const real k, const Point<int> &p1) : k(isinf(k) ? NAN : k), b(isinf(k) ? p1.x : (p1.y - k * p1.x)) {}

    Line(const real k, const real b) : k(k), b(b) {}

    Line perpendicular(const Point<int> &p1) const {
        if (isnan(k)) return Line(0, p1.y);
        else return Line(-1.0 / k, p1);
    }
};

struct Segment {
    Point<int> p1, p2;
    Line line;
    real length;

    Segment(const Point<int> &p1, const Point<int> &p2) : p1(p1), p2(p2), line(p1, p2) {
        length = distance(p1, p2);
    }
};

Point<real> lineIntersection(const Line &a, const Line &b) {
    if (isnan(a.k) && isnan(b.k) || a.k == b.k) throw;
    if (isnan(a.k)) return Point<real>(a.b, a.b * b.k + b.b);
    if (isnan(b.k)) return Point<real>(b.b, b.b * a.k + a.b);
    const real x = (b.b - a.b) / (a.k - b.k);
    const real y = a.k * x + a.b;
    return Point<real>(x, y);
}

bool pointOnSegment(const Point<real> &p, const Segment &s) {
    return dcmp(distance(p, s.p1) + distance(p, s.p2) - s.length);
}

bool segmentCircleIntersection(const Segment &s, const Point<int> &p, const real r) {
    Line v = s.line.perpendicular(p);
    Point<real> is = lineIntersection(v, s.line);
    real min, max;
    if (pointOnSegment(is, s)) {
        min = distance(is, p);
        max = std::max(distance(is, s.p1), distance(is, s.p2));
    } else {
        min = distance(p, s.p1);
        max = distance(p, s.p2);
        if (min > max) std::swap(min, max);
    }

    return (min < r || dcmp(min, r)) && (max > r || dcmp(max, r));
}

std::list<Ant> ants;
std::list<Ant>::iterator cakeOwner = ants.end();
Point<int> towers[MAXS];

inline void spawn() {
    if (ants.size() < 6) {
        if (map[0][0].reachable == false) return;

        static int cnt = -1;
        cnt++;
        ants.push_back(Ant(cnt / 6 + 1));
    }
}

inline void incMessage() {
    for (std::list<Ant>::const_iterator it = ants.begin(); it != ants.end(); it++) {
        it->position->message += it->hasCake ? 5 : 2;
    }
}

inline void move() {
    for (std::list<Ant>::iterator it = ants.begin(); it != ants.end(); it++) {
        // static int _cnt = 0;
        // _cnt++;
        // printf("move(): _cnt = %d\n", _cnt);

        int id = -1;
        // printf("move(): lastPosition = [%d, %d]\n", it->lastPosition.x, it->lastPosition.y);
        for (int i = 0; i < 4; i++) {
            Point<int> newPosition = it->position.offset(i);

            if (!newPosition.valid()) continue;
            if (newPosition == it->lastPosition) continue;
            if (!newPosition->reachable) continue;

            if (id == -1 || newPosition->message > it->position.offset(id)->message) {
                id = i;
            }
        }

        // if (id != -1) printf("move(): checking moving to [%d, %d]\n", it->position.offset(id).x, it->position.offset(id).y);

        if (id != -1 && (it->age() + 1) % 5 == 0) {
            // printf("move(): special, before = [%d, %d]\n", it->position.offset(id).x, it->position.offset(id).y);
            Point<int> newPosition;
            do {
                id = (id - 1 + 4) % 4;
                newPosition = it->position.offset(id);
            } while (!newPosition.valid() || !newPosition->reachable || newPosition == it->lastPosition);
            // printf("move(): special, after = [%d, %d]\n", it->position.offset(id).x, it->position.offset(id).y);
        }

        it->moveTo(it->position.offset(id));
    }
}

inline void getCake() {
    if (cakeOwner != ants.end()) return;

    for (std::list<Ant>::iterator it = ants.begin(); it != ants.end(); it++) {
        if (it->position == Point<int>(n, m)) {
            cakeOwner = it;
            it->hasCake = true;
            it->hp = std::min(it->hpLimit, it->hp + it->hpLimit / 2);
            // puts("getCake(): got");
            break;
        }
    }
}

inline void attack() {
    for (int i = 0; i < s; i++) {
        // static int _cnt = 0;
        // _cnt++;
        // printf("attack(): _cnt = %d\n", _cnt);

        std::list<Ant>::iterator target = ants.end();
        if (cakeOwner != ants.end() && cakeOwner->attackable(towers[i])) {
            target = cakeOwner;
        }

        if (target == ants.end()) {
            for (std::list<Ant>::iterator it = ants.begin(); it != ants.end(); it++) {
                real d = distance(it->position, towers[i]);
                if ((d < r || dcmp(d, r)) && (target == ants.end() || distance(it->position, towers[i]) < distance(target->position, towers[i]))) {
                    target = it;
                }
            }
        }

        if (target != ants.end()) {
            target->hp -= d;
            Segment s(towers[i], target->position);
            for (std::list<Ant>::iterator it = ants.begin(); it != ants.end(); it++) {
                if (it != target && segmentCircleIntersection(s, it->position, 0.5)) {
                    // printf("attack(): _cnt = %d, through [%d, %d]\n", _cnt, it->position.x, it->position.y);
                    it->hp -= d;
                }

                // if (it == target) printf("attack(): _cnt = %d, target [%d, %d]\n", _cnt, target->position.x, target->position.y);
            }
        }
    }
}

inline void kill() {
    for (std::list<Ant>::iterator it = ants.begin(); it != ants.end(); ) {
        if (it->hp < 0) {
            it->position->reachable = true;
            if (it == cakeOwner) cakeOwner = ants.end();
            it = ants.erase(it);
        } else it++;
    }
}

inline bool check() {
    for (std::list<Ant>::const_iterator it = ants.begin(); it != ants.end(); it++) {
        if (it->position == Point<int>(0, 0) && it->hasCake) return false;
    }

    return true;
}

inline void decMessage() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (map[i][j].message > 0) map[i][j].message--;
        }
    }
}

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

    scanf("%d %d\n%d %d %d", &n, &m, &s, &d, &r);
    for (int i = 0; i < s; i++) {
        scanf("%d %d", &towers[i].x, &towers[i].y);
        towers[i]->reachable = false;
    }
    scanf("%d", &t);

    time = 1;
    for (; time <= t; time++) {
        // printf("main(): time = %d\n", time);
        spawn();
        incMessage();
        move();
        getCake();
        attack();
        kill();
        if (!check()) break;
        decMessage();

        // for (std::list<Ant>::const_iterator it = ants.begin(); it != ants.end(); it++) printf("%d %d %d %d %d\n", it->age(), it->level, it->hp, it->position.y, it->position.x);
        // putchar('\n');
    }

    if (time > t) puts("The game is going on");
    else printf("Game over after %d seconds\n", time);

    printf("%d\n", ants.size());
    for (std::list<Ant>::const_iterator it = ants.begin(); it != ants.end(); it++) printf("%d %d %d %d %d\n", it->age(), it->level, it->hp, it->position.x, it->position.y);

    fclose(stdin);

    return 0;
}
最近的文章

「ZJOI2006」物流运输 - 最短路 + DP

物流公司要把一批货物从码头 A A 运到码头 B B 。由于货物量比较大,需要 n n 天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个 n n 天的运输计划,使得总成本尽可能地小。

于  BZOJ, COGS, DP, ZJOI, 最短路 继续阅读
更早的文章

「BZOJ 3156」防御准备 - 斜率优化 DP

我们定义战线为一条长度为 n n 的序列,在这条战线上共设有 n n 个检查点,从左到右依次标号为 1 1 n n 。一个战线为合法战线当且仅当任意一个检查点可以通过安全检查。对于第 i i 个点,通过安全检查的方法有两种,第一种是放置一个守卫塔,这将花费 c(i) c(i) 的费用,第二种方式是放置一个木偶,放置木偶的花费等于这个检查点右侧的第一个守卫塔到它的距离。第 n n 个点只能放置守卫塔。求最小的战线花费值。

于  BZOJ, DP, 单调队列, 斜率优化 继续阅读
comments powered by Disqus