#2068. 多边形下海

    ID: 2068 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest978来源:qoj.ac数据:公开样例计算几何

多边形下海

多边形下海

题目描述

标题: 多边形下海 - Problem - QOJ.ac

#4530. 多边形下海

Statistics

The problem was used in the following contests:

在一个二维空间中,给定一个凸多边形,假设该凸多边形的面密度为 ρ , 放入一个 水平面为 y=0 的无穷大的水池当中,水的密度为 1 ,求该凸多边形在静止并且势能到达最低点的情况下, 该凸多边形逆时针旋转了多少?

势能包括凸多边形本身的重力势能和浮力对其做功产生的浮力势能。

输入格式

第一行一个数 N ,表示数据组数。 对于每组数据: 第一行两个数,整数 n 和 浮点数 ρ, 表示多边形点的个数和多边形的密度。 接下来 n 行, 每行两个浮点数 x,y 逆时针表示凸包上的所有点。

输出格式

对于每一组数据输出一行,θ, 表示凸多边形达到势能的最低点的时候,其逆时针旋转的弧度是 多少,0≤θ<2π。

本题包含 Special Judge, 对于你的输出允许 10−6 的误差,请输出小数部分位数尽量多的数(但小数位数不要超过 15)。

样例一

输入

3
3 0.3
0.23272177 0.50274749
0.69314977 0.57621227
0.63404493 0.80356643
7 0.7
0.97651045  0.03790015
0.9919297   0.75416081
0.76345204  0.83482219
0.17087067  0.83086959
0.19621027  0.49532965
0.24676201  0.45389929
0.67563998  0.14424922
8 0.6
0.03726264  0.10180906
0.50450581  0.13303585
0.81055071  0.29025366
0.99405094  0.68868719
0.77510244  0.87181985
0.40531889  0.91965237
0.27990499  0.84662178
0.07581749  0.30329282

输出

2.60634462
3.83816499
2.50530629

解释

以上三组数据的可视化结果分别如下:

  • 绿色代表静止的多边形能量最低时的形态,
  • 灰色代表原始多边形,
  • 蓝色为水面

限制与约定

**时间限制:**1s

**空间限制:**256MB

凸多边形由逆时针给出。

数据组数 N≤10。

0.1<ρ<0.9。

0≤x,y≤1。

对于 30% 的数据, n=3;

对于 60% 的数据, n≤100;

对于 100% 的数据, n≤100000, ∑n≤100000。

数据保证能构成凸多边形,且多边形上相邻两点之间的距离不小于 10−10,且多边形的面积不小于 10−4。

数据保证唯一解

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
3 0.3
0.23272177 0.50274749
0.69314977 0.57621227
0.63404493 0.80356643
7 0.7
0.97651045  0.03790015
0.9919297   0.75416081
0.76345204  0.83482219
0.17087067  0.83086959
0.19621027  0.49532965
0.24676201  0.45389929
0.67563998  0.14424922
8 0.6
0.03726264  0.10180906
0.50450581  0.13303585
0.81055071  0.29025366
0.99405094  0.68868719
0.77510244  0.87181985
0.40531889  0.91965237
0.27990499  0.84662178
0.07581749  0.30329282
2.60634462
3.83816499
2.50530629