列表

详情

NC232262. 公平公正的风行迷踪

描述

题目背景
        
        原神要复刻风行迷踪啦！！！第一次风行迷踪可让嘤嘤非常的开心，因为嘤嘤和好朋友们玩的可开心啦（虽然好像某人视力有点问题），不过很可惜，嘤嘤并没有某NPC角色，不然可能乐趣还会更多一些，但这次复刻会不会再增添一份乐趣呢？在风行迷踪中，玩家被分成两个阵营，有一名猎手和多名游侠。其中，猎手有一个技能叫做感应光环，感应光环可以探索到一定半径内是否有游侠（只能知道是或否），CD时间为10秒，猎手还有一个叫做禁锢诅咒的限定技（只能使用一次），可以将一名游侠禁锢在原地30秒，如果猎手在180秒内捕获所有游侠，那么猎手将获得胜利，否则游侠将获得胜利。
        在这次游戏中，嘤嘤成为了猎手，眼看着时间一分一秒的过去了，她却还没捕获到任何游侠，她发现旅行者的力量是有极限的，所以她决定开G！！！在她的仙术加持下，感应光环和禁锢诅咒都得到了强化，感应光环强化成了可以探索到一定半径内一名游侠的位置，并且CD缩短为0，而禁锢诅咒强化成了同时对所有游侠生效。但是，还不够，嘤嘤发现时间来不及了，所以她急忙使用她的替身派蒙娜丽莎暂停了时间。（所以为什么既要暂停时间又要禁锢诅咒？难道是要防一手相同类型的替身？）
        现在，嘤嘤可以安安心心的找游侠了。

题目描述

        我们可以把风行迷踪的地图简化为一个坐标系下的正方形，正方形的四个顶点分别是  ，我们以上帝视角可以得知所有游侠的位置 (x,y) ，猎手和游侠都只能在正方形内进行探索或躲藏。由于所有游侠都被施加了禁锢诅咒，并且猎手暂停了时间，所以所有的游侠都可以看作是一个个隐藏的点。现在，猎手的感应光环技能的探索半径为 r （即猎手可以发现一名与她距离小于等于 r 的游侠）。猎手将从原点 (0,0) 出发，向 x 轴正方向开始进行探索，如果她在原点或前进过程中使用感应光环发现了游侠，她将改变方向朝着游侠前进，直到捕获游侠（此过程中，猎手不会使用感应光环），如果她在捕获了一个游侠后又通过感应光环发现了另一个游侠，那么她将向着下一个游侠的位置前进，否则她将不改变方向继续前进。若她到了正方形的边界或边角无法再前进时，她将沿着边界逆时针绕行。
        注意：在某一时刻，如果有多名游侠同时出现在感应光环的范围内，根据左手定则，猎手将只发现位置在正方形最左下角的游侠（最左下的定义为优先最左其次最下）。
        那么，嘤嘤想知道她能捕获多少名游侠？（一个游侠被捕获后，游侠将立刻从地图上消失）


输入描述

第一行两个整数 n ，  ， n 表示游侠数量， r 表示感应光环的半径。
接下来 n 行，每行两个整数 x_i ， ，表示游侠的位置 (x,y) 。
题目保证不会有位置相同的游侠，且原点没有游侠。

输出描述

一个整数，表示旅行者能捕获的游侠数。
并按捕获顺序输出游侠的编号。

示例1

输入: 

4 2
3 3
9 2
9 9
12 12

输出: 

2
2 3

示例2

输入: 

3 6
2 2
15 7
13 13

输出: 

2
1 3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 48ms, 内存消耗: 604K, 提交时间: 2022-01-01 00:42:36 

#include <bits/stdc++.h>
int main() {
    using namespace std;
    using LD = long double;
    using LL = long long;
    constexpr LD eps = 1e-10;
    struct P {
        LD x, y;
        LD dis(const P& p) const {
            return hypot(x - p.x, y - p.y);
        }
        LD dot(const P& p) const {
            return x * p.x + y * p.y;
        }
        P norm() const {
            LD d = hypot(x, y);
            return {x / d, y / d};
        }
        P r90() const {
            return {-y, x};
        }
        P operator + (const P& p) const {
            return {x + p.x, y + p.y};
        }
        P operator - (const P& p) const {
            return {x - p.x, y - p.y};
        }
        P operator * (LD k) const {
            return {x * k, y * k};
        }
    };
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    LD r;
    cin >> n >> r;
    vector<P> p(n);
    vector<int> cd(n), ans;
    for (auto& [x, y] : p) cin >> x >> y;
    P cur = {0, 0}, dir = {1, 0};
    int ch = 0;
    while (ch < 8) {
        //cout << cur.x << " " << cur.y << " " << dir.x << " " << dir.y << "\n";
        int s = -1;
        LD mt = -1;
        auto f = [](LD cur, LD dir) {
            if (abs(dir) < eps) return (LD)1E100;
            if (dir < 0) return cur / -dir;
            return (1000000 - cur) / dir;
        };
        LD xt = f(cur.x, dir.x), yt = f(cur.y, dir.y);
        auto update = [&](int i, double t) {
            if (t > xt + eps or t > yt + eps) return;
            if (s == -1) {
                s = i;
                mt = t;
            }
            if (mt > t) {
                s = i;
                mt = t;
            }
            if (mt == t and p[i].x < p[s].x) {
                s = i;
                mt = t;
            }
            if (mt == t and p[i].x == p[s].x and p[i].y < p[s].y) {
                s = i;
                mt = t;
            }
        };
        for (int i = 0; i < n; i += 1) if (not cd[i]) {
            if (cur.dis(p[i]) <= r + eps)
                update(i, 0);
            else {
                LD x = (p[i] - cur).dot(dir.r90());
                LD y = (p[i] - cur).dot(dir);
                if (y >= eps and abs(x) <= r + eps)
                    update(i, y - sqrt(max(r * r - x * x, LD(0))));
            }
        }
        if (s != -1) {
            cd[s] = 1;
            ans.push_back(s);
            dir = (p[s] - (cur + dir * mt)).norm();
            cur = p[s];
            ch = 0;
        }
        else {
            LD xt = f(cur.x, dir.x), yt = f(cur.y, dir.y);
            if (abs(xt - yt) < eps) {
                cur = cur + dir * xt;
                if (dir.x > 0 and dir.y > 0) dir = {-1, 0};
                else if (dir.x < 0 and dir.y > 0) dir = {0, -1};
                else if (dir.x < 0 and dir.y < 0) dir = {1, 0};
                else dir = {0, 1};
            }
            else if (xt < yt) {
                cur = cur + dir * xt;
                if (dir.x > 0) dir = {0, 1};
                else dir = {0, -1};
            }
            else {
                cur = cur + dir * yt;
                if (dir.y > 0) dir = {-1, 0};
                else dir = {1, 0};
            }
            ch += 1;
        }
    }
    cout << ans.size() << '\n';
    for (int x : ans) cout << x + 1 << " ";
    return 0;
}

上一题

© 2024 nowcoder.com