Advertisement
MystMe

Untitled

Nov 16th, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <tgmath.h>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. const double  pi = M_PI;
  8.  
  9.  
  10. // Структура, задающая одну точку
  11. struct Dot{
  12.     double x;
  13.     double y;
  14.  
  15.     Dot(double X, double Y) : x(X), y(Y) {}
  16. };
  17.  
  18. // Структура, задающая выпуклый многоугольник
  19. struct Polygon{
  20.     vector<Dot> points; // Точки граней
  21.  
  22.     void add_dot(double x, double y){
  23.         Dot tmp(x,y);
  24.         points.push_back(tmp);
  25.     }
  26. };
  27.  
  28. // Возвращает полярный угол для вектора, заданного двумя точками
  29. double polar_angle(Dot first, Dot Second){
  30.     double x = Second.x - first.x;
  31.     double y = Second.y - first.y;
  32.  
  33.     if(x > 0 && y >= 0) {
  34.         return atan(y/x);
  35.     }
  36.     if(x > 0 && y < 0) {
  37.         return atan(y/x) + 2*pi;
  38.     }
  39.     if(x < 0) {
  40.         return atan(y/x) + pi;
  41.     }
  42.     if(x == 0 && y > 0){
  43.         return pi/2;
  44.     }
  45.     if(x == 0 && y < 0){
  46.         return 3*pi/2;
  47.     }
  48. }
  49.  
  50. void cin_Polygon(Polygon& to_read, bool minus=false){
  51.     double size;
  52.     cin >> size;
  53.     int start = 0;
  54.     double min_x = 800001;
  55.     double min_y = 800001;
  56.     for(int i = 0; i < size; i++){
  57.         double x = 0;
  58.         double y = 0;
  59.  
  60.         cin >> x >> y;
  61.  
  62.         if(minus) {
  63.             x *= -1;
  64.             y *= -1;
  65.  
  66.             if(y < min_y) {
  67.                 min_x = x;
  68.                 min_y = y;
  69.                 start = i;
  70.             }
  71.             else if(y == min_y) {
  72.                 if(x <= min_x) {
  73.                     min_x = x;
  74.                     min_y = y;
  75.                     start = i;
  76.                 }
  77.             }
  78.             to_read.add_dot(x, y);
  79.         } else {
  80.             if(y < min_y) {
  81.                 min_x = x;
  82.                 min_y = y;
  83.                 start = i;
  84.             }
  85.             else if(y == min_y) {
  86.                 if(x <= min_x) {
  87.                     min_x = x;
  88.                     min_y = y;
  89.                     start = i;
  90.                 }
  91.             }
  92.             to_read.add_dot(x, y);
  93.         }
  94.     }
  95.  
  96.     std::rotate(to_read.points.begin(), to_read.points.begin()+start, to_read.points.end());
  97.  
  98.     size = to_read.points.size();
  99.     for(int i = 1; i < size/2; i++){
  100.         Dot tmp = to_read.points[i];
  101.         to_read.points[i] = to_read.points[size-i];
  102.         to_read.points[size-i] = tmp;
  103.     }
  104. }
  105.  
  106. // Разница Минковского:  Q - P = Q + (-P)
  107. Polygon min_diff(const Polygon& Q,const Polygon&  P){
  108.     int Q_size = Q.points.size(); // Количество точек в первом многоугольнике
  109.     int P_size = P.points.size(); // Количество точек во втором многоугольнике
  110.  
  111.     int Q_pointer = 0;  // Количество уже пройденных точек в первом
  112.     int P_pointer = 0;  // Количество уже пройденных точек во втором
  113.  
  114.     Polygon tmp;  // Многоугольник, хранящий разницу Q и P
  115.     while(Q_pointer < Q_size || P_pointer < P_size) {
  116.         double x_coor = Q.points[Q_pointer%Q_size].x + P.points[P_pointer%P_size].x;
  117.         double y_coor = Q.points[Q_pointer%Q_size].y + P.points[P_pointer%P_size].y;
  118.  
  119.         // cout << x_coor << " " << y_coor << "\n";
  120.         tmp.add_dot(x_coor, y_coor);
  121.  
  122.         double Q_angle = polar_angle(Q.points[Q_pointer%Q_size], Q.points[(Q_pointer + 1)%Q_size]);
  123.  
  124.         double P_angle = polar_angle(P.points[P_pointer%P_size], P.points[(P_pointer + 1)%P_size]);
  125.  
  126.         if (Q_angle == 0 && P_angle > pi) {
  127.             Q_angle = 2*pi;
  128.         }
  129.  
  130.         if (P_angle == 0 && Q_angle > pi) {
  131.             P_angle = 2*pi;
  132.         }
  133.  
  134.         if(Q_angle < P_angle){
  135.             Q_pointer++;
  136.         }
  137.         else if (P_angle < Q_angle){
  138.             P_pointer++;
  139.         }
  140.         else {
  141.             Q_pointer++;
  142.             P_pointer++;
  143.         }
  144.     }
  145.     return tmp;
  146. }
  147.  
  148. inline double isLeft(Dot P0, Dot P1, Dot P2 )
  149. {
  150.     return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x -  P0.x) * (P1.y - P0.y) );
  151. }
  152.  
  153. bool Check(Polygon tmp){
  154.     /*Dot P2(0,0);
  155.     for(int i = 0; i < tmp.points.size()-1;i++){
  156.         double side = isLeft(tmp.points[i], tmp.points[i+1], P2);
  157.         if(side <= 0) {
  158.             return false;
  159.         }
  160.     }
  161.     return true;*/
  162.     bool fl = false;
  163.     for(int z=0; z < tmp.points.size(); z++)
  164.     {
  165.         Dot p0 = tmp.points[z];
  166.         Dot p1 = tmp.points[(z+1)% tmp.points.size()];
  167.         Dot a(p1.x - p0.x, p1.y - p0.y);
  168.         Dot b(0 - p0.x, 0 - p0.y);
  169.         double sa = a.x*b.y-b.x*a.y;
  170.         if (sa>0) {
  171.             fl = true;
  172.         }
  173.         if (sa<0) {
  174.             return false;
  175.         }
  176.         if(p0.x == 0 and p0.y == 0
  177.                          or p1.x == 0 and p1.y == 0 or
  178.                                           sa==0 and !(a.x*b.x<0 or a.y*b.y<0) and
  179.                 !(pow(a.x, 2) + pow(a.y, 2) < pow(b.x, 2) + pow(b.y, 2))) {
  180.             return true;
  181.         }
  182.     }
  183.     return fl;
  184. }
  185.  
  186. int main() {
  187.     // Считываем многоугольник Q
  188.     Polygon Q;
  189.     cin_Polygon(Q);
  190.  
  191.     // Считываем многоугольник P
  192.     Polygon P;
  193.     cin_Polygon(P, true);
  194.  
  195.     Polygon tmp = min_diff(Q,P);
  196.     Dot T = tmp.points[0];
  197.     tmp.points.push_back(T);
  198.     bool ans = Check(tmp);
  199.  
  200.     if(ans){
  201.         cout << "YES";
  202.     }
  203.     else {
  204.         cout << "NO";
  205.     }
  206.  
  207.     return 0;
  208. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement