#P18734. [正睿NOI2021训练] 计算几何
[正睿NOI2021训练] 计算几何
计算几何
给定坐标范围为 的正方形平面区域,以及其中 个整点 ,这些点可以重合。
称一个正方形区域是“好的”,当且仅当它的四个顶点都是整点、四条边平行于坐标轴、完全位于上述范围内,并且其内部不包含任何给定点。给定点可以落在正方形边界上。
有 次询问,每次给出一个整点 ,求严格包含该点的最大“好的”正方形的面积。严格包含意味着询问点不能位于正方形边界。不存在时输出 。
输入格式
第一行一个正整数 ,表示测试数据组数。每组数据依次为:
- 一行两个整数 。
- 接下来 行,每行两个整数 。
- 一行一个正整数 。
- 接下来 行,每行两个整数 。
输出格式
每次询问输出一行一个整数,表示最大合法面积。
数据范围
,,,;所有点与询问坐标均为 内的整数。
样例 1
输入
1
5 5
1 4
2 1
3 2
4 1
4 4
3
3 1
2 3
4 3
输出
4
9
4