После войны сверхзвуковая ракета стала самым популярным видом общественным транспортом.
Каждая сверхзвуковая ракета состоит из двух «двигателей». Каждый двигатель представляет собой множество из «источников питания». Первый двигатель состоит из $$$n$$$ источников питания, а второй из $$$m$$$. Источник питания можно представить как точку $$$(x_i, y_i)$$$ на 2-D плоскости. Все точки в каждом двигателе различные.
Вы можете влиять на каждый двигатель отдельно. Есть два действия, которые вы можете делать с каждым двигателем. Вы можете делать каждое действие столько раз, сколько хотите.
- Каждый источник питания двигателя $$$(x_i, y_i)$$$ станет $$$(x_i+a, y_i+b)$$$, где $$$a$$$ и $$$b$$$ могут быть любыми действительными числами. Другими словами, все источники питания будут смещены.
- Каждый источник питания двигателя $$$(x_i, y_i)$$$ станет $$$(x_i \cos \theta - y_i \sin \theta, x_i \sin \theta + y_i \cos \theta)$$$, где $$$\theta$$$ может быть любым действительным числом. Другими словами, все источники питания будут повернуты.
Двигатель работает следующим способом: после того, как оба двигателя будут заряжены, их источники питания объединяются вместе (координаты источников питания разных двигателей могут совпадать). А именно, если есть две точки питания $$$A(x_a, y_a)$$$ и $$$B(x_b, y_b)$$$, то для каждого действительного числа $$$k$$$, такого что $$$0 \lt k \lt 1$$$, будет сгенерирован новый источник питания $$$C_k(kx_a+(1-k)x_b,ky_a+(1-k)y_b)$$$. Эта процедура будет повторена еще раз со всеми новыми и старыми источниками. После этого будет сгенерировано «силовое поле» из всех источников питания.
Сверхзвуковая ракета будет «безопасна» тогда и только тогда, когда после всех ваших действий на генераторы, уничтожение любого источника питания не изменит силовое поле (в сравнении со случаем, когда ни один источник питания не был уничтожен). Два силовые поля считаются одинаковыми тогда и только тогда, когда каждый источник питания в одном силовом поле принадлежит и второму.
У вас есть сверхзвуковая ракета, проверьте безопасна ли она.
Первая строка содержит два целых числа $$$n$$$, $$$m$$$ ($$$3 \le n, m \le 10^5$$$) — количество источников питания в каждом двигателе.
Каждая из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$0\leq x_i, y_i\leq 10^8$$$) — координаты $$$i$$$-го источника питания в первом двигателе.
Каждая из следующих $$$m$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$0\leq x_i, y_i\leq 10^8$$$) — координаты $$$i$$$-го источника питания во втором двигателе.
Гарантируется, что нет двух или более источников питания, которые находятся в одной точке, в каждом двигателе.
Выведите «YES», если сверхзвуковая ракета безопасна, иначе выведите «NO».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную).
3 4
0 0
0 2
2 0
0 2
2 2
2 0
1 1
YES
3 4
0 0
0 2
2 0
0 2
2 2
2 0
0 0
NO
Те точки, которые находятся близко друг к другу, на самом деле совпадают. Сначала, вы можете использовать второе действие над первым двигателем, где $$$\theta = \pi$$$ (вы поверните все точки на $$$180$$$ градусов).
После операции источники питания в первом двигателе будут иметь координаты $$$(0, 0)$$$, $$$(0, -2)$$$ и $$$(-2, 0)$$$.
Потом, вы можете использовать первое действие над вторым двигателем, где $$$a = b = -2$$$.
После операции источники питания во втором двигателе будут иметь координаты $$$(-2, 0)$$$, $$$(0, 0)$$$, $$$(0, -2)$$$ и $$$(-1, -1)$$$.
Можно заметить, что, уничтожая любую точку, силовое поле будет всегда выпуклым треугольником с координатами $$$(0, 0)$$$, $$$(-2, 0)$$$, $$$(0, -2)$$$.
Во втором примере не имеет значения как вы будете менять, во втором двигателе всегда будет источник питания, который изменит силовое поле, если будет уничтожен.
