Advertisement
Guest User

Untitled

a guest
Nov 15th, 2019
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. const double EPS = 1e-99;
  7.  
  8. class Vector;
  9.  
  10. class Point
  11. {
  12. public:
  13.     double x, y, z;
  14.     Point(double x, double y, double z) : x(x), y(y), z(z) {}
  15.     Point operator+(const Point& p);
  16.     Point operator+(const Vector* v);
  17.     Point operator-(const Vector* v);
  18.     bool operator==(const Point& p) const
  19.     {
  20.         return abs(x - p.x) < EPS && abs(y - p.y) < EPS && abs(z - p.z) < EPS;
  21.     }
  22.     Point operator!()
  23.     {
  24.         return Point(0-x, 0-y, 0-z);
  25.     }
  26.     bool operator<(const Point& p) const
  27.     {
  28.         if (x < p.x)
  29.             return true;
  30.         else if (x == p.x)
  31.             if (y < p.y)
  32.                 return true;
  33.         return false;
  34.     }
  35.     bool operator>(const Point& p) const
  36.     {
  37.         if (x > p.x)
  38.             return true;
  39.         else if (x == p.x)
  40.             if (y > p.y)
  41.                 return true;
  42.         return false;
  43.     }
  44.  
  45. };
  46.  
  47. class Vector
  48. {
  49. public:
  50.     double x, y, z;
  51.     Vector(double x, double y, double z) : x(x), y(y), z(z) {}
  52.     Vector(const Point& p0, const Point& p1) : x(p1.x - p0.x), y(p1.y - p0.y), z(p1.z - p0.z) {}
  53.     Vector operator+(const Vector& v) const;
  54.     Vector operator-(const Vector& v) const;
  55.     Vector operator*(double value) const;
  56.     double dot(const Vector& v);
  57.     double vec(const Vector& v);
  58.     double norm();
  59. };
  60.  
  61. double angle(Point p1, Point p2)
  62. {
  63.     Vector v1(p1, p2);
  64.     Vector v2(Point(0, 0, 0), Point(1, 0 , 0));
  65.  
  66.     double cos = v1.dot(v2) / (v1.norm() * v2.norm());
  67.     double arccos = acos(cos);
  68.  
  69.     double sin = v2.vec(v1)/ (v1.norm() * v2.norm());
  70.  
  71.     if (cos > 0)
  72.     {
  73.         if (sin >= 0)
  74.         {
  75.             return arccos + (M_PI / 2);
  76.         }
  77.         else
  78.         {
  79.             return (M_PI / 2) - arccos;
  80.         }
  81.     }
  82.     else
  83.     {
  84.         if (sin >= 0)
  85.         {
  86.             return arccos + (M_PI / 2);
  87.         }
  88.         else
  89.         {
  90.             return (5 * M_PI / 2) - arccos;
  91.         }
  92.     }
  93.  
  94. }
  95.  
  96. double angle2(Vector v1, Vector v2)
  97. {
  98.     double cos = v1.dot(v2) / (v1.norm() * v2.norm());
  99.     double arccos = acos(cos);
  100.  
  101.     return arccos;
  102. }
  103.  
  104. class Polygon
  105. {
  106. public:
  107.     Polygon() {}
  108.     Polygon(const std::vector<Point> &v, bool isReverse)
  109.     {
  110.         if (isReverse)
  111.         {
  112.             int indOfMinPoint = 0;
  113.             //находим минимальную точку в заданном направлении
  114.             for (int i = 1 ; i < v.size(); ++i)
  115.             {
  116.                 if (v[i] > v[indOfMinPoint])
  117.                     indOfMinPoint = i;
  118.             }
  119.             for (int i = 0 ; i < v.size(); ++i)
  120.             {
  121.                 vertices.push_back(v[indOfMinPoint % v.size()]);
  122.                 indOfMinPoint++;
  123.             }
  124.             Inverse();
  125.             return;
  126.         }
  127.  
  128.         int indOfMinPoint = 0;
  129.         //находим минимальную точку в заданном направлении
  130.         for (int i = 1 ; i < v.size(); ++i)
  131.         {
  132.             if (v[i] < v[indOfMinPoint])
  133.                 indOfMinPoint = i;
  134.         }
  135.         for (int i = 0 ; i < v.size(); ++i)
  136.         {
  137.             vertices.push_back(v[indOfMinPoint % v.size()]);
  138.             indOfMinPoint++;
  139.         }
  140.     }
  141.  
  142.     void AddVertex(Point p)
  143.     {
  144.         vertices.push_back(p);
  145.     }
  146.  
  147.     Point GetVertex(int ind) const
  148.     {
  149.         return vertices[ind];
  150.     }
  151.  
  152.     Point& operator[](int ind)
  153.     {
  154.         return vertices[ind];
  155.     }
  156.  
  157.     int VerticesCount() const
  158.     {
  159.         return vertices.size();
  160.     }
  161.  
  162.     void Inverse()
  163.     {
  164.         for (int i = 0; i < vertices.size(); ++i)
  165.         {
  166.             vertices[i] = !vertices[i];
  167.         }
  168.     }
  169.  
  170.     Polygon MinkSum(Polygon& pol2)
  171.     {
  172.         Polygon result;
  173.         int size1 = VerticesCount(), size2 = pol2.VerticesCount();
  174.         AddVertex(vertices[0]);
  175.         AddVertex(vertices[1]);
  176.         pol2.AddVertex(pol2[0]);
  177.         pol2.AddVertex(pol2[1]);
  178.         int i1 = 0, i2 = 0;
  179.         while (i1 < size1 || i2 < size2)
  180.         {
  181.             result.AddVertex(vertices[i1] + pol2.GetVertex(i2));
  182.             if (i2 >= size2)
  183.                 ++i1;
  184.             else if(i1 >= size1)
  185.                 ++i2;
  186.             else {
  187.                 if (angle(vertices[i1], vertices[i1 + 1]) < angle(pol2[i2], pol2[i2 + 1]))
  188.                     ++i1;
  189.                 else if (angle(vertices[i1], vertices[i1 + 1]) > angle(pol2[i2], pol2[i2 + 1]))
  190.                     ++i2;
  191.                 else
  192.                     ++i1, ++i2;
  193.             }
  194.         }
  195.         return result;
  196.     }
  197.  
  198. private:
  199.     std::vector<Point> vertices;
  200. };
  201.  
  202. bool Inside(Polygon& p)
  203. {
  204.     double sum = 0.0;
  205.     Point p0(0, 0, 0);
  206.     for (int i = 0; i < p.VerticesCount(); ++i)
  207.     {
  208.         if (p[i] == p0)
  209.             return false;
  210.         Vector v1(p0, p[i]), v2(p0, p[(i + 1) % p.VerticesCount()]);
  211.         double temp = angle2(v1, v2);
  212.         if (abs((temp - M_PI)) < EPS)
  213.             return false;
  214.         sum += temp;
  215.     }
  216.     return abs(sum - (2 * M_PI)) < EPS;
  217. }
  218.  
  219. int main()
  220. {
  221.     //while(true) {
  222.         std::vector<Point> v;
  223.  
  224.         float x, y, z = 0;
  225.         int count;
  226.         std::cin >> count;
  227.         for (int i = 0; i < count; ++i) {
  228.             std::cin >> x >> y;
  229.             v.push_back(Point(x, y, z));
  230.         }
  231.  
  232.         std::reverse(std::begin(v), std::end(v));
  233.         Polygon pol1(v, false);
  234.  
  235.        v.clear();
  236.        std::cin >> count;
  237.        for (int i = 0; i < count; ++i)
  238.        {
  239.            std::cin >> x >> y;
  240.            v.push_back(Point(x, y, z));
  241.        }
  242.        std::reverse(std::begin(v), std::end(v));
  243.        Polygon pol2(v, true);
  244.        pol1 = pol1.MinkSum(pol2);
  245.  
  246.  
  247.         bool flag = Inside(pol1);
  248.         if (flag)
  249.             std::cout << "YES";
  250.         else
  251.             std::cout << "NO";
  252.     //}
  253.     return 0;
  254. }
  255.  
  256.  
  257. Point Point::operator+(const Point& p)
  258. {
  259.     return Point(x + p.x, y + p.y, z + p.z);
  260. }
  261.  
  262. Point Point::operator+(const Vector* v)
  263. {
  264.     return Point(x + v->x, y + v->y, z + v->z);
  265. }
  266.  
  267. Point Point::operator-(const Vector* v)
  268. {
  269.     return Point(x - v->x, y - v->y, z - v->z);
  270. }
  271.  
  272.  
  273.  
  274.  
  275. Vector Vector::operator+(const Vector& v) const
  276. {
  277.     return Vector(x + v.x, y + v.y, z + v.z);
  278. }
  279.  
  280. Vector Vector::operator-(const Vector& v) const
  281. {
  282.     return Vector(x - v.x, y - v.y, z - v.z);
  283. }
  284.  
  285. Vector Vector::operator*(double value) const
  286. {
  287.     return Vector(x * value, y * value, z * value);
  288. }
  289.  
  290. double Vector::dot(const Vector& v)
  291. {
  292.     return (x * v.x + y * v.y + z * v.z);
  293. }
  294.  
  295. double Vector::vec(const Vector& v)
  296. {
  297.     return x *v.y - y * v.x;
  298. }
  299.  
  300. double Vector::norm()
  301. {
  302.     return sqrt(dot(*this));
  303. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement