QOJ.ac

QOJ

時間限制: 5 s 記憶體限制: 256 MB 總分: 100

#7350. 实习生测试

统计

考虑平面上的两个凸多边形。你可以任意平移第二个多边形,但不能进行旋转或翻转。请编写一个程序,寻找一个平移向量,使得第一个多边形与平移后的第二个多边形的并集面积恰好等于 $S$,或者判断这是不可能的。

输入格式

第一行包含两个整数 $n$ 和 $m$ 以及一个实数 $S$ ($3 \le n, m \le 2000, 0 \le S \le 10^{13}$),分别表示两个多边形的顶点数和期望的并集面积。面积值的小数点后最多有十位数字。

接下来的 $n$ 行,每行包含两个整数 $x_{1,i}$ 和 $y_{1,i}$ ($-10^6 \le x_{i}, y_{i} \le 10^6$):按逆时针顺序给出第一个多边形的顶点坐标。

接下来的 $m$ 行以类似格式描述第二个多边形。

保证两个多边形均为严格凸多边形:即任意多边形的任意三个顶点都不在同一直线上。

同时保证,对于任何满足 $\frac{|S' - S|}{\max\{1, |S|\}} \le 10^{-3}$ 的 $S'$,期望的平移向量是否存在的情况与给定的 $S$ 完全一致。

输出格式

第一行输出 “Yes” 或 “No”,表示是否能找到这样一个平移向量使得多边形并集的面积等于 $S$。

如果存在该平移向量,则在第二行输出两个实数 $dx$ 和 $dy$,表示第二个多边形的平移向量坐标。

如果你的答案所对应的多边形并集面积与 $S$ 的绝对误差或相对误差不超过 $10^{-4}$,则被视为正确。即,如果 $\hat{S}$ 是由你的平移向量计算出的精确面积值,当满足 $\frac{|\hat{S} - S|}{\max\{S, 1\}} \le 10^{-4}$ 时,答案被视为正确。

样例

样例输入 1

6 4 5.25
0 0
1 0
2 1
2 2
1 3
0 2
5 4
5 3
7 1
7 2

样例输出 1

Yes
-5.0 -2.0

样例输入 2

4 4 2.5
0 0
2 0
2 1
0 1
0 5
1 5
1 7
0 7

样例输出 2

No

说明

第一个样例测试的示意图如下:

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.