QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100 Hackable ✓

#5355. 多边形上天

統計

8102年,世界被两个超级大国瓜分------折线国和曲线国。

折线国崇尚折线科技,国民认为折线是世上最优美的图形,象征着不公的世界与他们正直天性的完美结合。 但这在曲线国人看来,就是一群冥顽不灵的家伙脑中的愚蠢想法罢了。 与折线国恰恰相反,曲线国崇尚曲线科技。按照曲线国的官方说法,曲线才是最优美的图形,代表着他们灵活的思维与这多变的世界。

因为观念的不同,两国之间摩擦不断。在看似和平的天空下,一场新的战争正在酝酿。

折线国最近在多边形理论上有所突破,折学家们发现,如果一个垂直地平面的二维多边形在天上被高速抛出,则在它落地的瞬间会产生巨大的冲击力。折线国军方根据这一理论,用轰炸机装载了大量多边形炸弹,准备突袭曲线国。

曲线国早就意识到战争的危险,听到打入折线国的间谍传来的情报,迅速展开防空部署。 作为曲线国军方的高级程序员,上级要求你计算出从天而降的多边形炸弹的着地点。

因为多边形垂直地平面,只需要在多边形所在的二维平面上考虑这一问题。$x$ 轴为地面,$y$ 轴指向天空,单位为米。 根据情报,多边形有 $n$ 个顶点,第 $i$ 个顶点坐标是 $(x_i,y_i)$,多边形炸弹质量均匀,从轰炸机抛出时只有水平速度 $v\,m/s$,和绕质心的角速度 $\omega$(顺时针,弧度制)。 作为曲线国的程序员,你深知平抛与圆周运动的曲线,只需稍作计算就能算出炸弹第一个着地点。

重力加速度 $g=9.8\,m/s^2$。不考虑空气阻力。 保证输入的多边形在地面以上。 保证输入的多边形是简单多边形。

problem_5355_1.png

输入格式

第一行,一个整数 $n$,表示多边形顶点个数。

第二行,两个整数 $v, \omega$,分别表示出使水平速度和角速度。

接下来 $n$ 行,每行两个整数 $x_i, y_i$,表示多边形顶点坐标。 多边形顶点坐标以逆时针顺序输入。

输出格式

输出一行,一个实数 $x$,表示多边形碰到地面的第一个点的水平坐标。

样例数据

样例输入

4
1 1
1 2
2 2
2 3
1 3

样例输出

2.23241417

子任务

答案的相对误差或绝对误差在 $10^{-4}$ 以内,就算作正确。

数据保证第一着地点唯一。

炸弹质心坐标是所有顶点坐标的平均值。

子任务

  • 任务1(10): $3 \leq n\leq 2\,000$,$\omega=0$,$0 \leq v \leq 1000$,$0 < x_i, y_i \leq 10^5$
  • 任务2(30): $3 \leq n\leq 200$,$0 \leq \omega \leq 100$,$0 \leq v \leq 1000$,$0 < x_i, y_i \leq 10^5$
  • 任务3(60): $3 \leq n\leq 2\,000$,$0 \leq v,\omega \leq 1000$,$0 < x_i, y_i \leq 10^5$
About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.