题库练习 咒语

A71482 | 咒语

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

面壁者罗辑希望在宇宙中标记出一个星球。

不过罗辑不能以地球为原点发送坐标,因为这会暴露地球位置。一条咒语由若干组坐标组成,当罗辑选定一个目标星球后,他将再选定几个其他的星球,(可能有重复),以选定的星球为原点构建坐标系,分别确定出目标星球的坐标,作为咒语的一部分。一个咒语是有效的,当且仅当这条咒语标记出的目标星球只有一个(也就是不会有同时两个星球满足这个咒语的标记)。

作为咒语研究所的一员,你不需要去标定星球,你只需要在咒语发出前判断这条咒语是否有效。罗辑的计划能否成功就取决于你了。

一共有 n 个星球,你已经有一个以地球为原点的星图,上面包括了这 n 个星球,罗辑还会发给你 m 条咒语,每条咒语有 k 组坐标,代表以选定的 k 个星球为原点的目标星球的坐标 为了简化题目,你可以把宇宙想象成二维的,也就是说,所有的坐标都是二维的。

输入格式

第一行一个整数 n,接下来 n 行每行两个整数,第 i+1 行是编号为 i 的星球的坐标;

接下来一个整数 m,表示 m 条咒语;

接下来 m 行,每行第一个数为 k,接下来 k 组整数x_i , y_i 为以某个星球建立坐标系中的目标星球的坐标。

输出格式

输出 m 行,对于第 i 行,如果第 i 条咒语不能标记唯一的一个星球,输出“ No solution.”(不含双引号),否则输出那个星球的编号。

输入输出样例

输入 #1
3
1 1
2 2
3 3
2
2 -1 -1 -2 -2
1 3 3
输出 #1
1
No solution.
C++ 编辑器
输入
输出