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测评打分。不知道怎么写?

首页