Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <tgmath.h>
- #include <algorithm>
- using namespace std;
- const double pi = atan(1.0) * 4.0;
- // Структура, задающая одну точку
- struct Dot{
- double x;
- double y;
- Dot(double X, double Y) : x(X), y(Y) {}
- };
- // Структура, задающая выпуклый многоугольник
- struct Polygon{
- vector<Dot> points; // Точки граней
- void add_dot(double x, double y){
- Dot tmp(x,y);
- points.push_back(tmp);
- }
- };
- // Возвращает полярный угол для вектора, заданного двумя точками
- double polar_angle(Dot first, Dot Second){
- pair<double, double> vec;
- vec.first = Second.x - first.x;
- vec.second = Second.y - first.y;
- double alpha = acos(vec.first/sqrt(pow(vec.first, 2) + pow(vec.second, 2)));
- if(vec.second < 0) {
- return 2*M_PI - alpha;
- }
- return alpha;
- }
- void cin_Polygon(Polygon& to_read, bool minus=false){
- double size;
- cin >> size;
- int start = 0;
- double min_x = 800001;
- double min_y = 800001;
- for(int i = 0; i < size; i++){
- double x = 0;
- double y = 0;
- cin >> x >> y;
- if(minus) {
- x *= -1;
- y *= -1;
- if(x <= min_y) {
- if(y <= min_x){
- min_x = x;
- min_y = y;
- start = i;
- }
- }
- to_read.add_dot(x, y);
- } else {
- if(y <= min_y) {
- if(x <= min_x){
- min_x = x;
- min_y = y;
- start = i;
- }
- }
- to_read.add_dot(x, y);
- }
- }
- std::rotate(to_read.points.begin(), to_read.points.begin()+start, to_read.points.end());
- size = to_read.points.size();
- for(int i = 1; i < size/2; i++){
- Dot tmp = to_read.points[i];
- to_read.points[i] = to_read.points[size-i];
- to_read.points[size-i] = tmp;
- }
- }
- // Разница Минковского: Q - P = Q + (-P)
- Polygon min_diff(const Polygon& Q,const Polygon& P){
- int Q_size = Q.points.size(); // Количество точек в первом многоугольнике
- int P_size = P.points.size(); // Количество точек во втором многоугольнике
- int Q_pointer = 0; // Количество уже пройденных точек в первом
- int P_pointer = 0; // Количество уже пройденных точек во втором
- Polygon tmp; // Многоугольник, хранящий разницу Q и P
- while(Q_pointer < Q_size || P_pointer < P_size) {
- double x_coor = Q.points[Q_pointer%Q_size].x + P.points[P_pointer%P_size].x;
- double y_coor = Q.points[Q_pointer%Q_size].y + P.points[P_pointer%P_size].y;
- // cout << x_coor << " " << y_coor << "\n";
- tmp.add_dot(x_coor, y_coor);
- double Q_angle = polar_angle(Q.points[Q_pointer%Q_size], Q.points[(Q_pointer + 1)%Q_size]);
- double P_angle = polar_angle(P.points[P_pointer%P_size], P.points[(P_pointer + 1)%P_size]);
- if(Q_angle < P_angle){
- Q_pointer++;
- }
- else if (P_angle < Q_angle){
- P_pointer++;
- }
- else {
- Q_pointer++;
- P_pointer++;
- }
- }
- return tmp;
- }
- inline double isLeft(Dot P0, Dot P1, Dot P2 )
- {
- return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y) );
- }
- bool Check(Polygon tmp){
- Dot P2(0,0);
- for(int i = 0; i < tmp.points.size()-1;i++){
- double side = isLeft(tmp.points[i], tmp.points[i+1], P2);
- if(side <= 0) {
- return false;
- }
- }
- return true;
- }
- int main() {
- // Считываем многоугольник Q
- Polygon Q;
- cin_Polygon(Q);
- // Считываем многоугольник P
- Polygon P;
- cin_Polygon(P, true);
- Polygon tmp = min_diff(Q,P);
- Dot T = tmp.points[0];
- tmp.points.push_back(T);
- bool ans = Check(tmp);
- if(ans){
- cout << "YES";
- }
- else {
- cout << "NO";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement