Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- const double EPS = 1e-99;
- class Vector;
- class Point
- {
- public:
- double x, y, z;
- Point(double x, double y, double z) : x(x), y(y), z(z) {}
- Point operator+(const Point& p);
- Point operator+(const Vector* v);
- Point operator-(const Vector* v);
- bool operator==(const Point& p) const
- {
- return abs(x - p.x) < EPS && abs(y - p.y) < EPS && abs(z - p.z) < EPS;
- }
- Point operator!()
- {
- return Point(0-x, 0-y, 0-z);
- }
- bool operator<(const Point& p) const
- {
- if (x < p.x)
- return true;
- else if (x == p.x)
- if (y < p.y)
- return true;
- return false;
- }
- bool operator>(const Point& p) const
- {
- if (x > p.x)
- return true;
- else if (x == p.x)
- if (y > p.y)
- return true;
- return false;
- }
- };
- class Vector
- {
- public:
- double x, y, z;
- Vector(double x, double y, double z) : x(x), y(y), z(z) {}
- Vector(const Point& p0, const Point& p1) : x(p1.x - p0.x), y(p1.y - p0.y), z(p1.z - p0.z) {}
- Vector operator+(const Vector& v) const;
- Vector operator-(const Vector& v) const;
- Vector operator*(double value) const;
- double dot(const Vector& v);
- double vec(const Vector& v);
- double norm();
- };
- double angle(Point p1, Point p2)
- {
- Vector v1(p1, p2);
- Vector v2(Point(0, 0, 0), Point(1, 0 , 0));
- double cos = v1.dot(v2) / (v1.norm() * v2.norm());
- double arccos = acos(cos);
- double sin = v2.vec(v1)/ (v1.norm() * v2.norm());
- if (cos > 0)
- {
- if (sin >= 0)
- {
- return arccos + (M_PI / 2);
- }
- else
- {
- return (M_PI / 2) - arccos;
- }
- }
- else
- {
- if (sin >= 0)
- {
- return arccos + (M_PI / 2);
- }
- else
- {
- return (5 * M_PI / 2) - arccos;
- }
- }
- }
- double angle2(Vector v1, Vector v2)
- {
- double cos = v1.dot(v2) / (v1.norm() * v2.norm());
- double arccos = acos(cos);
- return arccos;
- }
- class Polygon
- {
- public:
- Polygon() {}
- Polygon(const std::vector<Point> &v, bool isReverse)
- {
- if (isReverse)
- {
- int indOfMinPoint = 0;
- //находим минимальную точку в заданном направлении
- for (int i = 1 ; i < v.size(); ++i)
- {
- if (v[i] > v[indOfMinPoint])
- indOfMinPoint = i;
- }
- for (int i = 0 ; i < v.size(); ++i)
- {
- vertices.push_back(v[indOfMinPoint % v.size()]);
- indOfMinPoint++;
- }
- Inverse();
- return;
- }
- int indOfMinPoint = 0;
- //находим минимальную точку в заданном направлении
- for (int i = 1 ; i < v.size(); ++i)
- {
- if (v[i] < v[indOfMinPoint])
- indOfMinPoint = i;
- }
- for (int i = 0 ; i < v.size(); ++i)
- {
- vertices.push_back(v[indOfMinPoint % v.size()]);
- indOfMinPoint++;
- }
- }
- void AddVertex(Point p)
- {
- vertices.push_back(p);
- }
- Point GetVertex(int ind) const
- {
- return vertices[ind];
- }
- Point& operator[](int ind)
- {
- return vertices[ind];
- }
- int VerticesCount() const
- {
- return vertices.size();
- }
- void Inverse()
- {
- for (int i = 0; i < vertices.size(); ++i)
- {
- vertices[i] = !vertices[i];
- }
- }
- Polygon MinkSum(Polygon& pol2)
- {
- Polygon result;
- int size1 = VerticesCount(), size2 = pol2.VerticesCount();
- AddVertex(vertices[0]);
- AddVertex(vertices[1]);
- pol2.AddVertex(pol2[0]);
- pol2.AddVertex(pol2[1]);
- int i1 = 0, i2 = 0;
- while (i1 < size1 || i2 < size2)
- {
- result.AddVertex(vertices[i1] + pol2.GetVertex(i2));
- if (i2 >= size2)
- ++i1;
- else if(i1 >= size1)
- ++i2;
- else {
- if (angle(vertices[i1], vertices[i1 + 1]) < angle(pol2[i2], pol2[i2 + 1]))
- ++i1;
- else if (angle(vertices[i1], vertices[i1 + 1]) > angle(pol2[i2], pol2[i2 + 1]))
- ++i2;
- else
- ++i1, ++i2;
- }
- }
- return result;
- }
- private:
- std::vector<Point> vertices;
- };
- bool Inside(Polygon& p)
- {
- double sum = 0.0;
- Point p0(0, 0, 0);
- for (int i = 0; i < p.VerticesCount(); ++i)
- {
- if (p[i] == p0)
- return false;
- Vector v1(p0, p[i]), v2(p0, p[(i + 1) % p.VerticesCount()]);
- double temp = angle2(v1, v2);
- if (abs((temp - M_PI)) < EPS)
- return false;
- sum += temp;
- }
- return abs(sum - (2 * M_PI)) < EPS;
- }
- int main()
- {
- //while(true) {
- std::vector<Point> v;
- float x, y, z = 0;
- int count;
- std::cin >> count;
- for (int i = 0; i < count; ++i) {
- std::cin >> x >> y;
- v.push_back(Point(x, y, z));
- }
- std::reverse(std::begin(v), std::end(v));
- Polygon pol1(v, false);
- v.clear();
- std::cin >> count;
- for (int i = 0; i < count; ++i)
- {
- std::cin >> x >> y;
- v.push_back(Point(x, y, z));
- }
- std::reverse(std::begin(v), std::end(v));
- Polygon pol2(v, true);
- pol1 = pol1.MinkSum(pol2);
- bool flag = Inside(pol1);
- if (flag)
- std::cout << "YES";
- else
- std::cout << "NO";
- //}
- return 0;
- }
- Point Point::operator+(const Point& p)
- {
- return Point(x + p.x, y + p.y, z + p.z);
- }
- Point Point::operator+(const Vector* v)
- {
- return Point(x + v->x, y + v->y, z + v->z);
- }
- Point Point::operator-(const Vector* v)
- {
- return Point(x - v->x, y - v->y, z - v->z);
- }
- Vector Vector::operator+(const Vector& v) const
- {
- return Vector(x + v.x, y + v.y, z + v.z);
- }
- Vector Vector::operator-(const Vector& v) const
- {
- return Vector(x - v.x, y - v.y, z - v.z);
- }
- Vector Vector::operator*(double value) const
- {
- return Vector(x * value, y * value, z * value);
- }
- double Vector::dot(const Vector& v)
- {
- return (x * v.x + y * v.y + z * v.z);
- }
- double Vector::vec(const Vector& v)
- {
- return x *v.y - y * v.x;
- }
- double Vector::norm()
- {
- return sqrt(dot(*this));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement