logo AlgoBeat OnlineJudge
登录 注册

#10081. [Sleeping Cup #8] B. Super Laser Gun

内存限制:8 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

注记:

本题存在赛时原版和赛后加强版两个版本,此处为赛后加强版。

本题的空间限制为 8 MB。

X 国最近在和 Y 国战斗。

X 国刚刚部署了一种激光武器,这种激光武器可以朝前后左右四个方向发射可以秒杀、无法防御的激光。

X 国的将领对这种武器十分重视,因为这种武器只能使用一次。

经过调查,他发现 Y 国的营地可以被激光破坏,并且可以被穿透。

现在 X 国的将领想要知道,是否有 Y 国的营地没有被破坏。

X 国的将领会向你进行多次询问,每次给出武器的坐标,询问是否有 Y 国的营地没有被破坏。

如果有,请告诉他没有被破坏的营地的最小编号。

维护一个下标从 开始的序列 (初始为空,允许出现重复元素),其中的每一项均为二维整点。

你需要实现以下三个功能:

  1. 清空。
  2. 的末尾添加一个二维整点。
  3. 中查询满足以下要求的元素(二维整点)的下标:
    • 该点与给定的二维整点不重合。
    • 该点与给定的二维整点之间连成的线段不平行于坐标轴:既不平行于 轴,也不平行于 轴。
    • 中不存在满足上述两个要求且下标小于该点的点。

请使用以下模板:

#include <bits/stdc++.h>
#include "laser.h"
using namespace std;
// ...
void clear()
{
	// ...
}
void add(int x, int y)
{
	// ...
}
int query(int x, int y)
{
	// ...
	return 0;
}
int main()
{
	cout << "";
	start();
}
  • 对于 clear() 函数:
    • 调用该函数时,程序应当将 清空。
    • 该函数在单个测试点中最多调用 次。
    • 保证不会在第一次调用该函数前调用其他函数。
  • 对于 add(x, y) 函数:
    • 调用该函数时,程序应当向 的末尾添加整点
    • 保证
    • 该函数在单个测试点中最多调用 次。
  • 对于 query(x, y) 函数:
    • 调用该函数时,程序应当返回 中符合要求的那个元素的编号。
    • 特别地,如果 中没有符合要求的元素,程序应当返回
    • 保证
    • 该函数在单个测试点中最多调用 次。
  • 你不必关注 main() 函数(及其调用的 start() 函数)的具体内容。
  • 你可以在 clear() 函数的注释前定义全局变量。

样例

样例 1

调用函数 返回值
clear();
query(1, 1);
query(1, 2);
query(2, 1);
query(2, 2);
add(1, 1);
query(1, 1);
query(1, 2);
query(2, 1);
query(2, 2);
add(2, 2);
query(1, 1);
query(1, 2);
query(2, 1);
query(2, 2);
clear();
query(1, 1);
query(1, 2);
query(2, 1);
query(2, 2);
add(2, 2);
query(1, 1);
query(1, 2);
query(2, 1);
query(2, 2);
add(1, 1);
query(1, 1);
query(1, 2);
query(2, 1);
query(2, 2);

样例 2

调用函数 返回值
clear();
query(1, 2);
query(2, 2);
query(3, 3);
add(1, 3);
query(1, 2);
query(2, 2);
query(3, 3);
add(3, 3);
query(1, 2);
query(2, 2);
query(3, 3);
clear();
query(1, 2);
query(2, 2);
query(3, 3);
add(3, 3);
query(1, 2);
query(2, 2);
query(3, 3);
add(1, 3);
query(1, 2);
query(2, 2);
query(3, 3);