Advertisement
MystMe

Untitled

Nov 16th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.31 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 = atan(1.0) * 4.0;
  8.  
  9. // Структура, задающая одну точку
  10. struct Dot{
  11.     double x;
  12.     double y;
  13.  
  14.     Dot(double X, double Y) : x(X), y(Y) {}
  15. };
  16.  
  17. // Структура, задающая выпуклый многоугольник
  18. struct Polygon{
  19.     vector<Dot> points; // Точки граней
  20.  
  21.     void add_dot(double x, double y){
  22.         Dot tmp(x,y);
  23.         points.push_back(tmp);
  24.     }
  25. };
  26.  
  27. // Возвращает полярный угол для вектора, заданного двумя точками
  28. double polar_angle(Dot first, Dot Second){
  29.     pair<double, double> vec;
  30.     vec.first = Second.x - first.x;
  31.     vec.second = Second.y - first.y;
  32.     double alpha = acos(vec.first/sqrt(pow(vec.first, 2) + pow(vec.second, 2)));
  33.     if(vec.second < 0) {
  34.         return 2*M_PI - alpha;
  35.     }
  36.     return alpha;
  37. }
  38.  
  39. void cin_Polygon(Polygon& to_read, bool minus=false){
  40.     double size;
  41.     cin >> size;
  42.     int start = 0;
  43.     double min_x = 800001;
  44.     double min_y = 800001;
  45.     for(int i = 0; i < size; i++){
  46.         double x = 0;
  47.         double y = 0;
  48.  
  49.         cin >> x >> y;
  50.  
  51.         if(minus) {
  52.             x *= -1;
  53.             y *= -1;
  54.  
  55.             if(x <= min_y) {
  56.                 if(y <= min_x){
  57.                     min_x = x;
  58.                     min_y = y;
  59.                     start = i;
  60.                 }
  61.             }
  62.             to_read.add_dot(x, y);
  63.         } else {
  64.             if(y <= min_y) {
  65.                 if(x <= min_x){
  66.                     min_x = x;
  67.                     min_y = y;
  68.                     start = i;
  69.                 }
  70.             }
  71.             to_read.add_dot(x, y);
  72.         }
  73.     }
  74.  
  75.     std::rotate(to_read.points.begin(), to_read.points.begin()+start, to_read.points.end());
  76.  
  77.     size = to_read.points.size();
  78.     for(int i = 1; i < size/2; i++){
  79.         Dot tmp = to_read.points[i];
  80.         to_read.points[i] = to_read.points[size-i];
  81.         to_read.points[size-i] = tmp;
  82.     }
  83. }
  84.  
  85. // Разница Минковского:  Q - P = Q + (-P)
  86. Polygon min_diff(const Polygon& Q,const Polygon&  P){
  87.     int Q_size = Q.points.size(); // Количество точек в первом многоугольнике
  88.     int P_size = P.points.size(); // Количество точек во втором многоугольнике
  89.  
  90.     int Q_pointer = 0;  // Количество уже пройденных точек в первом
  91.     int P_pointer = 0;  // Количество уже пройденных точек во втором
  92.  
  93.     Polygon tmp;  // Многоугольник, хранящий разницу Q и P
  94.     while(Q_pointer < Q_size || P_pointer < P_size) {
  95.         double x_coor = Q.points[Q_pointer%Q_size].x + P.points[P_pointer%P_size].x;
  96.         double y_coor = Q.points[Q_pointer%Q_size].y + P.points[P_pointer%P_size].y;
  97.  
  98.         // cout << x_coor << " " << y_coor << "\n";
  99.         tmp.add_dot(x_coor, y_coor);
  100.  
  101.         double Q_angle = polar_angle(Q.points[Q_pointer%Q_size], Q.points[(Q_pointer + 1)%Q_size]);
  102.  
  103.         double P_angle = polar_angle(P.points[P_pointer%P_size], P.points[(P_pointer + 1)%P_size]);
  104.  
  105.  
  106.         if(Q_angle < P_angle){
  107.             Q_pointer++;
  108.         }
  109.         else if (P_angle < Q_angle){
  110.             P_pointer++;
  111.         }
  112.         else {
  113.             Q_pointer++;
  114.             P_pointer++;
  115.         }
  116.     }
  117.     return tmp;
  118. }
  119.  
  120. inline double isLeft(Dot P0, Dot P1, Dot P2 )
  121. {
  122.     return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x -  P0.x) * (P1.y - P0.y) );
  123. }
  124.  
  125. bool Check(Polygon tmp){
  126.     Dot P2(0,0);
  127.     for(int i = 0; i < tmp.points.size()-1;i++){
  128.         double side = isLeft(tmp.points[i], tmp.points[i+1], P2);
  129.         if(side <= 0) {
  130.             return false;
  131.         }
  132.     }
  133.     return true;
  134. }
  135.  
  136. int main() {
  137.     // Считываем многоугольник Q
  138.     Polygon Q;
  139.     cin_Polygon(Q);
  140.  
  141.     // Считываем многоугольник P
  142.     Polygon P;
  143.     cin_Polygon(P, true);
  144.  
  145.     Polygon tmp = min_diff(Q,P);
  146.     Dot T = tmp.points[0];
  147.     tmp.points.push_back(T);
  148.     bool ans = Check(tmp);
  149.  
  150.     if(ans){
  151.         cout << "YES";
  152.     }
  153.     else {
  154.         cout << "NO";
  155.     }
  156.  
  157.     return 0;
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement