#P4074. [Wf2014]Crane Balancing

    ID: 1751 传统题 1000ms 128MiB 尝试: 25 已通过: 10 难度: 6 上传者: 标签>CF1900普及+/提高-鞋带公式叉积有理数精确运算向下取整与向上取整多边形重心

[Wf2014]Crane Balancing

题目描述

作为刚刚从蓝翔毕业的优秀学子,你成为了一名吊车司机。

在施工作业中,你必须时刻保证吊车的平衡,如果吊起的重物太重或太轻,你的吊车就会因失去平衡而倒下。

现在, ACM(The Association of Crane Manufacturers)\text{ACM(The Association of Crane Manufacturers)} 公司准备请既会玩吊车,又能码代码的你来设计一款吊车平衡计算软件。

为了方便起见,我们将吊车视作一个密度均匀的 nn 边形,其顶点依次标号为 1…n1\dots n,挂载重物的吊钩就是 11 号点。

现在要在编号为 11 的端点放上一个大小忽略不计的重物,问放的重物的重量在什么区间内,才能使这个多边形保持平衡(不会往左或往右翻)。

输入格式

输入数据的第一行是一个整数 nn,代表这个多边形的边数。

之后 nn 行,每行两个整数,依次代表这个多边形的第 1,2,…,n1, 2, \dots , n 号点的坐标。

输出格式

输出只有一行,代表吊起的重物质量的闭区间 [a,b][a,b],注意左端点向下取整,右端点向上取整。

例如,如果区间为 [1.5,13.3][1.5,13.3],则输出 1 .. 14\text{1 .. 14}。

若区间为 [a,+∞)[a,+\infty),则输出 ⌊a⌋ .. inf\lfloor a \rfloor \text{ .. inf}。

如果吊车不能承载任何质量的重物,则输出 unstable\text{unstable}。

7
50 50
0 50
0 0
30 0
30 30
40 40
50 40
0 .. 1017

数据规模与约定

对于 100%100\% 的数据满足,$3 \leq n \leq 100, -2000 \leq x_i \leq 2000, 0\leq y_i \leq 2000$。