Advertisement
MystMe

Untitled

Nov 16th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.57 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(y < min_y) {
  56.                 min_x = x;
  57.                 min_y = y;
  58.                 start = i;
  59.             }
  60.             else if(y == min_y) {
  61.                 if(x <= min_x) {
  62.                     min_x = x;
  63.                     min_y = y;
  64.                     start = i;
  65.                 }
  66.             }
  67.             to_read.add_dot(x, y);
  68.         } else {
  69.             if(y < min_y) {
  70.                 min_x = x;
  71.                 min_y = y;
  72.                 start = i;
  73.             }
  74.             else if(y == min_y) {
  75.                 if(x <= min_x) {
  76.                     min_x = x;
  77.                     min_y = y;
  78.                     start = i;
  79.                 }
  80.             }
  81.             to_read.add_dot(x, y);
  82.         }
  83.     }
  84.  
  85.     std::rotate(to_read.points.begin(), to_read.points.begin()+start, to_read.points.end());
  86.  
  87.     size = to_read.points.size();
  88.     for(int i = 1; i < size/2; i++){
  89.         Dot tmp = to_read.points[i];
  90.         to_read.points[i] = to_read.points[size-i];
  91.         to_read.points[size-i] = tmp;
  92.     }
  93. }
  94.  
  95. // Разница Минковского:  Q - P = Q + (-P)
  96. Polygon min_diff(const Polygon& Q,const Polygon&  P){
  97.     int Q_size = Q.points.size(); // Количество точек в первом многоугольнике
  98.     int P_size = P.points.size(); // Количество точек во втором многоугольнике
  99.  
  100.     int Q_pointer = 0;  // Количество уже пройденных точек в первом
  101.     int P_pointer = 0;  // Количество уже пройденных точек во втором
  102.  
  103.     Polygon tmp;  // Многоугольник, хранящий разницу Q и P
  104.     while(Q_pointer < Q_size || P_pointer < P_size) {
  105.         double x_coor = Q.points[Q_pointer%Q_size].x + P.points[P_pointer%P_size].x;
  106.         double y_coor = Q.points[Q_pointer%Q_size].y + P.points[P_pointer%P_size].y;
  107.  
  108.         // cout << x_coor << " " << y_coor << "\n";
  109.         tmp.add_dot(x_coor, y_coor);
  110.  
  111.         double Q_angle = polar_angle(Q.points[Q_pointer%Q_size], Q.points[(Q_pointer + 1)%Q_size]);
  112.  
  113.         double P_angle = polar_angle(P.points[P_pointer%P_size], P.points[(P_pointer + 1)%P_size]);
  114.  
  115.  
  116.         if(Q_angle < P_angle){
  117.             Q_pointer++;
  118.         }
  119.         else if (P_angle < Q_angle){
  120.             P_pointer++;
  121.         }
  122.         else {
  123.             Q_pointer++;
  124.             P_pointer++;
  125.         }
  126.     }
  127.     return tmp;
  128. }
  129.  
  130. inline double isLeft(Dot P0, Dot P1, Dot P2 )
  131. {
  132.     return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x -  P0.x) * (P1.y - P0.y) );
  133. }
  134.  
  135. bool Check(Polygon tmp){
  136.     Dot P2(0,0);
  137.     for(int i = 0; i < tmp.points.size()-1;i++){
  138.         double side = isLeft(tmp.points[i], tmp.points[i+1], P2);
  139.         if(side <= 0) {
  140.             return false;
  141.         }
  142.     }
  143.     return true;
  144. }
  145.  
  146. int main() {
  147.     // Считываем многоугольник Q
  148.     Polygon Q;
  149.     cin_Polygon(Q);
  150.  
  151.     // Считываем многоугольник P
  152.     Polygon P;
  153.     cin_Polygon(P, true);
  154.  
  155.     Polygon tmp = min_diff(Q,P);
  156.     Dot T = tmp.points[0];
  157.     tmp.points.push_back(T);
  158.     bool ans = Check(tmp);
  159.  
  160.     if(ans){
  161.         cout << "YES";
  162.     }
  163.     else {
  164.         cout << "NO";
  165.     }
  166.  
  167.     return 0;
  168. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement