首页 > 其他分享 >扫描游戏

扫描游戏

时间:2023-02-12 12:11:06浏览次数:35  
标签:cnt last 游戏 idx int 扫描 物件 return

问题描述

有一根围绕原点 �O 顺时针旋转的棒 ��OA, 初始时指向正上方 (Y 轴正向)。 在平面中有若干物件, 第 �i 个物件的坐标为 (��,��)(xi​,yi​), 价值为 ��zi​ 。当棒扫到某个 物件时, 棒的长度会瞬间增长 ��zi​, 且物件瞬间消失(棒的顶端恰好碰到物件也 视为扫到), 如果此时增长完的棒又额外碰到了其他物件, 也按上述方式消去 (它和上述那个点视为同时消失)。

如果将物件按照消失的时间排序, 则每个物件有一个排名, 同时消失的物 件排名相同, 请输出每个物件的排名, 如果物件永远不会消失则输出 −1−1 。

输入格式

输入第一行包含两个整数 �、�n、L, 用一个空格分隔, 分别表示物件数量和棒 的初始长度。

接下来 �n 行每行包含第三个整数 ��,��,��xi​,yi​,zi​ 。

输出格式

输出一行包含 �n 整数, 相邻两个整数间用一个空格分隔, 依次表示每个物件的排名。

样例输入

5 2
0 1 1
0 3 2
4 3 5
6 8 1
-51 -33 2

样例输出

1 1 3 4 -1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const ll INF = 9e18;
struct point
{
    ll x, y, z;
    int id;
}a[maxn];

int Quadrant(point a)
{
    if(a.x >= 0 && a.y > 0)return 1;//y的正半轴放到第一象限
    if(a.x > 0 && a.y <= 0)return 2;//x的正半轴放到第二象限
    if(a.x <= 0 && a.y < 0)return 3;
    return 4;
}
ll cross(point a, point b)//求两个点的叉积
{
    return a.x * b.y - a.y * b.x;
}
bool cmp(point a, point b)//两个点进行排序
{
    if(Quadrant(a) == Quadrant(b))//象限相同
    {
        if(cross(a, b) == 0)//方向相同
            return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;//按照离原点的距离排序
        else
           return cross(a, b) < 0;//方向不同,顺时针排序
    }
    else
        return Quadrant(a) < Quadrant(b);//不同象限直接排序
}

//线段树数组 
ll mi[maxn << 2];
void push_up(int o)
{
    mi[o] = min(mi[o << 1], mi[o << 1 | 1]);
}
//建树,线段树维护最小值,维护离原点的距离的平方 
void build(int o, int l, int r)
{
    if(l == r)
    {
        mi[o] = a[l].x * a[l].x + a[l].y * a[l].y;
        return ;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    push_up(o);
}

//更新idx=x的值为val:保证一个点第一次触碰到之后消除 
void update(int o, int l, int r, int x, ll val)
{
    if(l == r)
    {
        mi[o] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)update(o << 1, l, mid, x, val);
    else update(o << 1 | 1, mid + 1, r, x, val);
    push_up(o);
}


//判断节点o的值是否小于等于z^2 
inline bool check(int o, ll z)
{
    if(mi[o] == INF) return false;//此时节点o已经被消除
    if(z > 2000000000)return true;//z过大对它进行平方会溢出
    return mi[o] <= z * z;
}

///找区间[L,R]中从左往右第一个小于等于z^2的数字,找到的答案存储在idx里面 
ll idx;
bool query(int o, int l, int r, int L, int R, ll z)
{
    if(L > R)return false;
    if(l == r)
    {
        idx = l;
        return check(o, z);
    }
    int mid = (l + r) >> 1;
    if(L <= mid)
    {
        //左子树的最小值不超过z^2 
        if(check(o << 1, z) && query(o << 1, l, mid, L, R, z))
            return true;
    }
    if(R > mid)
    {
        //右子树的最小值不超过z^2 
        if(check(o << 1 | 1, z) && query(o << 1 | 1, mid + 1, r, L, R, z))
            return true;
    }
    return false;
}
int ans[maxn];

int main()
{
    ll n, L;
    cin >> n >> L;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].x >> a[i].y >> a[i].z;
        a[i].id = i;
        ans[i] = -1;
    }
    //点按照顺时针排序 
    sort(a + 1, a + 1 + n, cmp);
    //建树 
    build(1, 1, n);
    int cnt = 0;        //当前的排名 
    int lastcnt = 0;    //上一个位置的排名 
    int last = 0;          //上一个位置的idx 
    while(true)
    {
        //查找区间[last + 1, n] 
        bool ok = query(1, 1, n, last + 1, n, L);
        if(ok)L = L + a[idx].z;
        else
        {
            //[last + 1, n]没找到,继续从区间[1, last - 1]找 
            ok = query(1, 1, n, 1, last - 1, L);
            if(ok)L = L + a[idx].z;
            else break;    //都没找到直接跳出循环 
        }
        //将idx出的点更新为INF 
        update(1, 1, n, idx, INF);
        if(last)
        {
            //如果存在上一个位置 && 上一个位置的坐标、方向和当前的一致,则排名不变 
            if(Quadrant(a[last]) == Quadrant(a[idx]) && cross(a[last], a[idx]) == 0)
                ans[a[idx].id] = lastcnt, ++cnt;
            else
                ans[a[idx].id] = ++cnt, lastcnt = cnt;
        }
        else
            ans[a[idx].id] = ++cnt, lastcnt = cnt;
        last = idx;
    }
    for(int i = 1; i <= n; i++)
    {
        cout<<ans[i];
        if(i != n)cout<<" ";
    }
    return 0;
}

 

标签:cnt,last,游戏,idx,int,扫描,物件,return
From: https://www.cnblogs.com/weinan030416/p/17113612.html

相关文章

  • 分享一个好用的目录扫描工具
    dirmap!!!dirmap是一个一个高级web目录扫描工具,功能将会强于DirBuster、Dirsearch、cansina、御剑功能特点支持n个target*n个payload并发支持递归扫描支持自定义需要递归扫描的......
  • 收购、被收购、卸任,古永锵经历的行业剧变与权力游戏
    创办优酷十一年,经历了中国在线视频行业从无到繁盛的曲折,古永锵一次次解开难题,但最终,这位视频行业的元老却没能掌控自己的命运。10月31日,阿里巴巴集团CEO张勇通过内......
  • 蜗牛式学习Java--基础篇(2)--综合案例拼图游戏
      创建窗体代码:packagecom.ktestdemo;importjavax.swing.*;//继承JFramepublicclassPictureFrameextendsJFrame{//定义构造方法public......
  • 游戏类C程序设计
    1迷宫游戏1.1MAZE1.0#include<iostream>usingnamespacestd;intmain(){intx=1,y=2,mx=10,my=9;charch;cout<<"ready!\n";while(true)......
  • Python黑客编程之暴力字典web扫描器
    描述通过读取字典中的关键字,拼接成url,来测试目标站点文件目录结构代码设置了一个resume参数,如果因为网络等问题导致扫描中断,重新启动扫描时可以将resume设置为上次......
  • 「解题报告」[省选联考 2021 A 卷] 矩阵游戏
    啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会......
  • 扫描仪对象 java 230211
    功能接收用户从键盘输入的内容扫描仪的用法......
  • Python黑客编程之拓印web扫描器
    描述遍历cms网站的本地目录,作为参考来扫描远程网站的目录和文件实现用os.walk实现嵌套目录的遍历用多线程发起requests请求,考虑线程安全,变量应装在队列中而不是列表......
  • 游戏中的分享功能怎么做更有效
    本文首发于微信公众号【小蚂蚁教你做游戏】,欢迎关注领取更多学习做游戏的原创教程资料,每天学点儿游戏开发知识。嗨!大家好,我是小蚂蚁。在制作新游戏【彩虹星球大冒险】的时候......
  • 《植物大战僵尸》 辅助编写5—— 编写wpf游戏辅助
    这里一开始用了Pinvoke.net,后来发现它的WriteProcessMemory接口和win32APi里的WriteProcessMemory不太一样。就抄了一个其他的。internalpartialclassCheatCore......