CF1017E.The Supersonic Rocket
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
After the war, the supersonic rocket became the most common public transportation.
Each supersonic rocket consists of two "engines". Each engine is a set of "power sources". The first engine has n power sources, and the second one has m power sources. A power source can be described as a point (xi,yi) on a 2-D plane. All points in each engine are different.
You can manipulate each engine separately. There are two operations that you can do with each engine. You can do each operation as many times as you want.
- For every power source as a whole in that engine: (xi,yi) becomes (xi+a,yi+b), a and b can be any real numbers. In other words, all power sources will be shifted.
- For every power source as a whole in that engine: (xi,yi) becomes (xicosθ−yisinθ,xisinθ+yicosθ), θ can be any real number. In other words, all power sources will be rotated.
The engines work as follows: after the two engines are powered, their power sources are being combined (here power sources of different engines may coincide). If two power sources A(xa,ya) and B(xb,yb) exist, then for all real number k that 0<k<1, a new power source will be created Ck(kxa+(1−k)xb,kya+(1−k)yb). Then, this procedure will be repeated again with all new and old power sources. After that, the "power field" from all power sources will be generated (can be considered as an infinite set of all power sources occurred).
A supersonic rocket is "safe" if and only if after you manipulate the engines, destroying any power source and then power the engine, the power field generated won't be changed (comparing to the situation where no power source erased). Two power fields are considered the same if and only if any power source in one field belongs to the other one as well.
Given a supersonic rocket, check whether it is safe or not.
战争结束后,超音速火箭成为了最常见的公共交通工具。
每枚超音速火箭由两个“引擎”组成。每个引擎是一组“能源源”。第一个引擎有 n 个能源源,第二个引擎有 m 个能源源。每个能源源可表示为二维平面上的一个点 (xi,yi)。每个引擎内的所有点互不相同。
你可以分别操控每个引擎。对每个引擎,你可执行以下两种操作(每种操作可执行任意多次):
- 对该引擎中所有能源源整体执行:(xi,yi) 变为 (xi+a,yi+b),其中 a 和 b 可为任意实数。换言之,所有能源源将被一同平移。
- 对该引擎中所有能源源整体执行:(xi,yi) 变为 (xicosθ−yisinθ,xisinθ+yicosθ),其中 θ 可为任意实数。换言之,所有能源源将被一同旋转。
引擎的工作方式如下:当两个引擎启动后,它们的能源源被合并(此时不同引擎的能源源可能重合)。若存在两个能源源 A(xa,ya) 和 B(xb,yb),则对所有满足 0<k<1 的实数 k,将生成一个新的能源源 Ck(kxa+(1−k)xb,kya+(1−k)yb)。随后,该过程将在所有新旧能源源之间重复进行。最终,由所有出现过的能源源构成一个“能量场”(可视为所有曾出现过的能源源组成的无限集合)。
一枚超音速火箭是“安全的”,当且仅当:在你对引擎进行任意操控之后,删除任意一个能源源再启动引擎,所生成的能量场与未删除任何能源源时完全相同(即二者一致)。两个能量场被视为相同,当且仅当其中一个场中的每个能源源也都属于另一个场。
给定一枚超音速火箭,请判断它是否安全。
输入格式
The first line contains two integers n, m (3≤n,m≤105) — the number of power sources in each engine.
Each of the next n lines contains two integers xi and yi (0≤xi,yi≤108) — the coordinates of the i-th power source in the first engine.
Each of the next m lines contains two integers xi and yi (0≤xi,yi≤108) — the coordinates of the i-th power source in the second engine.
It is guaranteed that there are no two or more power sources that are located in the same point in each engine.
第一行包含两个整数 n、m(3≤n,m≤105)—— 分别表示两台引擎中电源的数量。
接下来的 n 行,每行包含两个整数 xi 和 yi(0≤xi,yi≤108)—— 表示第一台引擎中第 i 个电源的坐标。
再接下来的 m 行,每行包含两个整数 xi 和 yi(0≤xi,yi≤108)—— 表示第二台引擎中第 i 个电源的坐标。
保证在每台引擎中,不存在两个或更多位于同一点的电源。
输出格式
Print "YES" if the supersonic rocket is safe, otherwise "NO".
You can print each letter in an arbitrary case (upper or lower).
如果超音速火箭是安全的,则输出 “YES”,否则输出 “NO”。
每个字母可以以任意大小写(大写或小写)输出。
输入输出样例
输入#1
3 4 0 0 0 2 2 0 0 2 2 2 2 0 1 1
输出#1
YES
输入#2
3 4 0 0 0 2 2 0 0 2 2 2 2 0 0 0
输出#2
NO
说明/提示
The first sample:
Those near pairs of blue and orange points actually coincide.
First, manipulate the first engine: use the second operation with θ=π (to rotate all power sources 180 degrees).
The power sources in the first engine become (0,0), (0,−2), and (−2,0).

Second, manipulate the second engine: use the first operation with a=b=−2.
The power sources in the second engine become (−2,0), (0,0), (0,−2), and (−1,−1).

You can examine that destroying any point, the power field formed by the two engines are always the solid triangle (0,0), (−2,0), (0,−2).
In the second sample, no matter how you manipulate the engines, there always exists a power source in the second engine that power field will shrink if you destroy it.
第一个样例:
图中靠近的蓝色与橙色点对实际上重合。
首先,操作第一台引擎:使用第二种操作,取 θ=π(将所有能量源旋转 180∘)。
第一台引擎中的能量源变为 (0,0)、(0,−2) 和 (−2,0)。

其次,操作第二台引擎:使用第一种操作,取 a=b=−2。
第二台引擎中的能量源变为 (−2,0)、(0,0)、(0,−2) 和 (−1,−1)。

你可以验证:无论摧毁哪一个点,两台引擎共同形成的有效能量场始终是顶点为 (0,0)、(−2,0)、(0,−2) 的实心三角形。
在第二个样例中,无论怎样操作引擎,第二台引擎中总存在某个能量源——一旦摧毁它,有效能量场便会缩小。
输入解题思路,AI测评打分。不知道怎么写?