#P11806. [PA 2017] 马赛克
[PA 2017] 马赛克
题目背景
译自 PA 2017 R3T1。
题目描述
给定二维平面上的 个整点。第 个点的坐标是 。
构造 个正方形,其中第 个正方形的左下角顶点是 ,满足以下条件:
- 这 个正方形的并是一个矩形;
- 任取 ,正方形 的交面积为 。(也就是说,正方形的边缘可以重合,但正方形不能相交。)
输入格式
本题单个测试点内有多组测试数据。
第一行,正整数 ,表示测试数据组数。接下来依次描述 组测试数据。
每组测试数据中,第一行一个正整数 。
接下来 行,每行两个非负整数 。
输出格式
对于每组测试数据输出一行:
如果不可能,输出一行一个 。
否则输出 ,其中正整数 表示正方形 的边长。
你需要保证 。保证如果存在解,则存在一组 的合法解。
3
2
0 0
0 1
2
3 2
2 3
4
1 1
2 1
3 1
1 2
TAK 1 1
NIE
TAK 1 1 3 2
提示
- ;
- ,;
- ;
- 如果存在解,则存在 的合法解。