AT_ttpc2015_h.包囲
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
包围
在二维平面上有N个被涂了颜色的坐标点,选择其中几个这样的点,并将这些点连接成简单的多边形。在多种选择可能性中,找出能把原点(0,0)包含进去,并且面积最小的多边形,求出其面积。
简单的多边形就是指自己不能互相交叉(边不能交叉)。
输入格式
N
X_1 Y_1
X_2 Y_2
:
X_N Y_N
- 第一行是被涂色的坐标点N(1 ≤ N ≤ 200) ,整数。
- 1+i行是第i个被涂色坐标点的坐标(X_i,Y_i)。
- 坐标数字范围是−100000 ≤X_i,Y_i≤ 100000
- 坐标不重复(X_i,Y_i)≠(X_j,Y_j)(i≠j)
- 坐标没有原点(X_i,Y_i)≠(0,0)
输出格式
- 如果找不到能够包含原点的多边形的话只输出一行Impossible。
- 如果能找到,第一行输出Possible,第二行输出面积最小值。
- 如果忘了换行或者面积跟标准答案有10^-8以下的误差的话,算正确。
输入输出样例
输入1 输出1
3 Possible
-1 -1 3.0000000000
1 -1
0 2
输入2 输出2
4 Possible
-1 -1 4.0000000000
1 -1
1 1
-1 1
输入3 输出3
3 Impossible
-1 -1
1 -1
1 1
输入输出样例
输入#1
3 -1 -1 1 -1 0 2
输出#1
Possible 3.0000000000
输入#2
4 -1 -1 1 -1 1 1 -1 1
输出#2
Possible 4.0000000000
输入#3
3 -1 -1 1 -1 1 1
输出#3
Impossible
说明/提示
输入1解释
这3个点连成的三角形就是包含原点,面积最小的简单多边形。
输入2解释
这4个点连成的矩形就是包含原点的多边形中,面积最小的。注意点的连接顺序不同,可能会无法形成简单多边形。
输入3解释
原点的位置实在这3个点连接成的三角形的边上,不符合把原点包含进去的条件,所以不存在包含原点的简单多边形。
输入解题思路,AI测评打分。不知道怎么写?