Beam Cannon
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 225 Accepted Submission(s): 87
Problem Description
Recently, the γ galaxies broke out Star Wars. Each planet is warring for resources. In the Star Wars, Planet X is under attack by other planets. Now, a large wave of enemy spaceships is approaching. There is a very large Beam Cannon on the Planet X, and it is very powerful, which can destroy all the spaceships in its attack range in a second. However, it takes a long time to fill the energy of the Beam Cannon after each shot. So, you should make sure each shot can destroy the enemy spaceships as many as possible.
To simplify the problem, the Beam Cannon can shot at any area in the space, and the attack area is rectangular. The rectangle parallels to the coordinate axes and cannot rotate. It can only move horizontally or vertically. The enemy spaceship in the space can be considered as a point projected to the attack plane. If the point is in the rectangular attack area of the Beam Cannon(including border), the spaceship will be destroyed.
To simplify the problem, the Beam Cannon can shot at any area in the space, and the attack area is rectangular. The rectangle parallels to the coordinate axes and cannot rotate. It can only move horizontally or vertically. The enemy spaceship in the space can be considered as a point projected to the attack plane. If the point is in the rectangular attack area of the Beam Cannon(including border), the spaceship will be destroyed.
Input
Input contains multiple test cases. Each test case contains three integers N(1<=N<=10000, the number of enemy spaceships), W(1<=W<=40000, the width of the Beam Cannon’s attack area), H(1<=H<=40000, the height of the Beam Cannon’s attack area) in the first line, and then N lines follow. Each line contains two integers x,y (-20000<=x,y<=20000, the coordinates of an enemy spaceship).
A test case starting with a negative integer terminates the input and this test case should not to be processed.
A test case starting with a negative integer terminates the input and this test case should not to be processed.
Output
Output the maximum number of enemy spaceships the Beam Cannon can destroy in a single shot for each case.
Sample Input
2 3 4
0 1
1 0
3 1 1
-1 0
0 1
1 0
-1
Sample Output
2
2
题意:
给出 N,W,H,代表有 N 个点还有一个 W 长 H 高的矩形。现用这个矩形覆盖,问最多能覆盖给出的点中有多少个。
思路:
线段树 + 扫描线。以每个点作为中心,建立一个矩形范围,说明这个矩形的中心放在这个区域中,就能够覆盖这个点。在建完所有的矩形后,求某个区域被矩形覆盖最多,这个区域被矩形覆盖数即为所求。用扫描线即可求出。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 10005 * 2; typedef struct { double y1, y2, x; int temp; } node; int n, m, ans; double yy[MAX]; node no[MAX]; int cover[MAX * 5], Max[MAX * 5]; bool cmp (node a, node b) { if (a.x != b.x) return a.x < b.x; return a.temp > b.temp; } void push_down (int node) { cover[node << 1] += cover[node]; cover[node << 1 | 1] += cover[node]; Max[node << 1] += cover[node]; Max[node << 1 | 1] += cover[node]; cover[node] = 0; } void push_up (int node) { Max[node] = max(Max[node << 1], Max[node << 1 | 1]); } void updata (int node, int l, int r, int cl, int cr, int c) { if (cl > r || cr < l) return; if (cl <= l && cr >= r) { cover[node] += c; Max[node] += c; return; } push_down(node); int mid = (r + l) >> 1; if (cl <= mid) updata(node << 1, l, mid, cl, cr, c); if (cr > mid) updata(node << 1 | 1, mid + 1, r, cl, cr, c); push_up(node); } int main() { double w, h; while (~scanf("%d", &n) && n != -1) { scanf("%lf%lf", &w, &h); m = 0, ans = 0; for (int i = 1; i <= n; ++i) { double x, y; scanf("%lf%lf", &x, &y); yy[m++] = y + h / 2; yy[m++] = y - h / 2; no[ans].y1 = y - h / 2; no[ans].y2 = y + h / 2; no[ans].x = x - w / 2; no[ans++].temp = 1; no[ans].y1 = y - h / 2; no[ans].y2 = y + h / 2; no[ans].x = x + w / 2; no[ans++].temp = -1; } sort(yy, yy + m); m = unique(yy, yy + m) - yy; sort(no, no + ans, cmp); memset(cover, 0, sizeof(cover)); memset(Max, 0, sizeof(Max)); int res = 0; for (int i = 0; i < ans; ++i) { int cl = lower_bound(yy, yy + m, no[i].y1) - yy; int cr = lower_bound(yy, yy + m, no[i].y2) - yy; updata(1, 0, m - 1, cl, cr, no[i].temp); res = max(res, Max[1]); } printf("%d\n", res); } return 0; }
相关推荐
cannon lide 110扫描仪 驱动
3d模型
cannon算法的简单实现,比较简单的一个实现算法实例
该算法是cannon的并行算法的发送接收MPI的实现
基于MPI的cannon算法,实现矩阵的相乘
矩阵相乘运算的cannon算法,适用于方阵间的高性能算法
cannon—L140驱动适合于winxp及vista
这是一款基于Cannon.js和Three.js的3d文字特效。该特效在屏幕上构建炫酷的3D文字特效,鼠标可以和文字进行交互。
仿微信小游戏“跳一跳”,使用three.js实现3D效果,cannon-es实现物理效果,结合vite+vue进行界面效果展示。
经典的cannon算法,主要用于矩阵相乘的并行求解问题。这个实现简单易懂,里面有详细注释。
前端项目-cannon.js,用javascript编写的轻量级3D物理引擎。
Master-Worker模式是常用的并行设计模式。它的核心思想是,系统有两个进程协议工作:Master进程和Worker进程。Master进程负责接收和分配任务,Worker进程负责处理子任务。当各个Worker进程将子任务处理完后,将结果...
yarn add three cannon-es用法为cannon-es-debugger对您的“三场景”对象和Cannon物理物体的引用: import { Scene } from 'three'import { World } from 'cannon-es'import cannonDebugger from 'cannon-es-...
HTML5 WebGL+Three.js+Cannon.js实现的3D立体十字关卡碰撞动画源码.zip
MPI源文件:Cannon并行实现及加速比分析
三加农炮 将THREE.Mesh转换为CANNON.Shape,并使用简化的形状进行可选的优化。用法安装: npm install -- save three - to - cannon 进口: // ES6import { threeToCannon } from 'three-to-cannon' ;// ...
cannon佳能2900驱动 ,下载解压,安装打印机以后,安装软件可以使用
cannon方法计算矩阵相乘
cannon eos digital sdk programming api reference 佳能EOS相机api开发文档
Cannon Lide25驱动