企业专业网站设计公,坑梓网站建设咨询,微商系统软件开发,浙江省工程建设监理管理协会网站【题目描述】
有一根围绕原点 O 顺时针旋转的棒 OA#xff0c;初始时指向正上方#xff08;Y 轴正向#xff09;。
在平面中有若干物件#xff0c;第 i 个物件的坐标为#xff08;,)#xff0c;价值为 。
当棒扫到某个物件时#xff0c;棒的长度会瞬间增长 #xff…【题目描述】
有一根围绕原点 O 顺时针旋转的棒 OA初始时指向正上方Y 轴正向。
在平面中有若干物件第 i 个物件的坐标为,)价值为 。
当棒扫到某个物件时棒的长度会瞬间增长 且物件瞬间消失棒的顶端恰好碰到物件也视为扫到如果此时增长完的棒又额外碰到了其他物件也按上述方式消去它和上述那个点视为同时消失。
如果将物件按照消失的时间排序则每个物件有一个排名同时消失的物件排名相同请输出每个物件的排名如果物件永远不会消失则输出 −1。
所有物品坐标两两不同。
【输入格式】
输入第一行包含两个整数 n、L用一个空格分隔分别表示物件数量和棒的初始长度。
接下来 n 行每行包含第三个整数,, 。
【输出格式】
输出一行包含 n 整数相邻两个整数间用一个空格分隔依次表示每个物件的排名。
【数据范围】
对于 30% 的评测用例1≤n≤500 对于 60% 的评测用例1≤n≤5000 对于所有评测用例1≤n≤200000− ≤ , ≤ 1 ≤ L, ≤ 。
【输入样例】 5 2 0 1 1 0 3 2 4 3 5 6 8 1 -51 -33 2 【输出样例】 1 1 3 4 -1 【思路】 题解来源AcWing 4649. 扫描游戏 - AcWing 【代码】
#include bits/stdc.h
typedef long long LL;
const int N 2e5 10;
const __int128 INF 1e38;
int n, ans[N], idx;
__int128 len;template typename T //快读模板
inline T fastread(T x)
{x 0;T w 1;char ch 0;while (ch 0 || ch 9){if (ch -)w -1;ch getchar();}while (ch 0 ch 9){x x * 10 (ch - 0);ch getchar();}return x x * w;
}struct point
{LL x, y, z;int id;
} a[N];
int Quadrant(point a) //因为棒是顺时针旋转我们这里把正常意义下的二四象限调换一下
{if (a.x 0 a.y 0)return 1;if (a.x 0 a.y 0)return 2;if (a.x 0 a.y 0)return 3;elsereturn 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;return cross(a, b) 0;}return Quadrant(a) Quadrant(b);
}//线段树
struct
{__int128 minv;
} seg[N * 4]; //线段树维护的是点到原点的距离的区间最小值
void pushup(int id)
{seg[id].minv std::min(seg[id 1].minv, seg[id 1 | 1].minv);
}
void build(int id, int l, int r)
{if (l r)seg[id].minv a[l].x * a[l].x a[l].y * a[l].y;else{int mid l r 1;build(id 1, l, mid);build(id 1 | 1, mid 1, r);pushup(id);}
}
void change(int id, int l, int r, int pos, __int128 val)
{if (l r)seg[id].minv val;else{int mid l r 1;if (pos mid)change(id 1, l, mid, pos, val);elsechange(id 1 | 1, mid 1, r, pos, val);pushup(id);}
}
int search(int id, int l, int r, int ql, int qr, __int128 val) //线段树上二分模板
//返回[ql,qr]这段区间里从左至右第一个小于等于val的元素的下标不存在就返回-1
{if (l ql r qr) //此时的区间正好是询问区间{if (seg[id].minv val) //如果整个区间的最小值都大于val直接返回-1return -1;else{if (l r)return l;int mid l r 1;if (seg[id 1].minv val) //如果左儿子里有这样的元素直接进入左儿子即可return search(id 1, l, mid, ql, mid, val);else //否则进入右儿子return search(id 1 | 1, mid 1, r, mid 1, qr, val);}return seg[id].minv;}int mid l r 1;if (qr mid)return search(id 1, l, mid, ql, qr, val);else if (ql mid)return search(id 1 | 1, mid 1, r, ql, qr, val);else{int pos search(id 1, l, mid, ql, mid, val);if (pos -1)return search(id 1 | 1, mid 1, r, mid 1, qr, val);elsereturn pos;}
}
signed main()
{// 注意用了快读就不能关闭流同步不然大概率会炸fastread(n), fastread(len);for (int i 1; i n; i) //初始化ans数组ans[i] -1;for (int i 1; i n; i){fastread(a[i].x), fastread(a[i].y), fastread(a[i].z);a[i].id i;}std::sort(a 1, a n 1, cmp);build(1, 1, n);int last 0; // last维护上一个扫到的点int rank 0; // rank记录扫到点的排名int lastrank 0; // 维护lastrank主要是为了处理有几个点极角相同的特殊情况根据题意它们的排名相同while (true){int idx -1;if (last 1 n) //一定要记得这句ifidx search(1, 1, n, last 1, n, len * len);if (idx ! -1)len a[idx].z;else{if (last 2) //一定要记得这句ifidx search(1, 1, n, 1, last - 1, len * len);if (idx ! -1)len a[idx].z;}if (idx -1) //没能找到可以划到的点退出死循环break;change(1, 1, n, idx, INF); //对于扫过的点我们可以把它单点修改成无穷大等价于它消失了if (last 0)ans[a[idx].id] rank, lastrank rank;else{if (Quadrant(a[last]) Quadrant(a[idx]) cross(a[last], a[idx]) 0) //该点和上一个点是同时被扫到的所以排名要一样ans[a[idx].id] lastrank, rank;elseans[a[idx].id] rank, lastrank rank;}last idx;}for (int i 1; i n; i)printf(%d , ans[i]);printf(\n);return 0;
}
