Fivt_3/task-C/30.11.2017 (MF)

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <iterator>


struct Point {
	int  x;
	int  y;
	int number;
	Point(int _x, int _y,int _number = -1):
			x(_x),
			y(_y),
			number(_number)
	{
	}

	Point(const Point& other) {
		x = other.x;
		y = other.y;
		number = other.number;
	}
	bool operator==(const Point& other) const;
	bool operator!=(const Point& other) const;
	Point operator+(const Point& other) const;
	Point operator-(const Point& other) const;
	double operator^(int p) const;
	double operator*(const Point& other) const;
	double GetModule() const;
	void Print() const;
};

Point operator-(const Point& point) {
	return {-point.x,-point.y};
}


bool Point::operator==(const Point &other) const{
	return (this->x == other.x && this->y == other.y);
}


bool Point::operator!=(const Point &other) const{
	return (this->x != other.x || this->y != other.y);
}


Point Point::operator+(const Point &other) const {
	return Point(this->x + other.x, this->y + other.y);
}


Point Point::operator-(const Point& other) const{
	return {this->x - other.x, this->y - other.y};
}


double Point::operator*(const Point &other) const{
	return (this->x*other.x + this->y*other.y);
}

double Point::GetModule() const {
	return std::sqrt( this->x*this->x + this->y*this->y);
}

void Point::Print() const {
	std::cout<<this->x<<' '<<this->y<<std::endl;
}


double VectorMultiplication(const Point &p1, const Point &p2) {
	return p1.x*p2.y - p2.x*p1.y;
}

double AngleBetweenVectors( const Point& p1, const Point& p2) {
	double cos = (p1*p2) / (p1.GetModule()*p2.GetModule());
	return std::acos(cos);
}


struct Edge {
	Point p1;
	Point p2;
	Edge(const Point& _p1, const Point& _p2);
	Edge(const Edge& edge); // copy-constructor
	Point PivotAroundEdge(const std::vector<Point> &points);
	bool operator==(const Edge& other) const;
};


Edge::Edge(const Point& _p1, const Point& _p2) :
		p1(_p1),
		p2(_p2)
{
}


Edge::Edge(const Edge& edge) :
		p1(edge.p1),
		p2(edge.p2)
{
}


bool Edge::operator==(const Edge& other) const{
	return (this->p1 == other.p1 && this->p2 == other.p2 ||
			this->p1 == other.p2 && this->p2 == other.p1);
}


double IsRightRotation(const Point& p1, const Point& p2, const Point& p3) {
	Point p1p2 = p2 - p1;
	Point p1p3 = p3 - p1;
	return VectorMultiplication(p1p3, p1p2);
}

bool IsIntersectionBetweenEdges(const Edge& edge1, const Edge& edge2) {

	bool difference1 = (IsRightRotation(edge1.p1,edge1.p2, edge2.p1) * //true
	IsRightRotation(edge1.p1,edge1.p2, edge2.p2) ) <= 0;

	bool difference2 = ( IsRightRotation(edge2.p1,edge2.p2, edge1.p1) * //false
	IsRightRotation(edge2.p1,edge2.p2, edge1.p2) ) < 0;

	return  difference1*difference2;
}


bool IsPointOnSegment( const Point& point1, const Point& point2, const Point& point) {
//	if ( point.x <= std::max(segment.p1.x, segment.p2.x) &&
//		 point.x >= std::min(segment.p1.x, segment.p2.x) ) {
//		if (point.y <= std::max(segment.p1.y, segment.p2.y) &&
//			point.y >= std::min(segment.p1.y, segment.p2.y) ) {
//			return IsRightRotation(segment.p1, segment.p2 , point) == 0;
//		} else { return false; }
//	}  else { return false; }
	Point VectorA = point - point1;
	Point VectorB = point - point2;
	return ( VectorA*VectorB  + VectorA.GetModule() * VectorB.GetModule() ) == 0;
}


class ConvexPolygon {
private:
	std::vector<Point> points;
public:
	ConvexPolygon(const std::vector<Point>& points);
	void Reverse();
	void CounterClockOrder();
	std::vector<Point> GetPoints() const;
	void Print() const;
	bool BruteForce( const Point& point ) const;
};


ConvexPolygon::ConvexPolygon(const std::vector<Point>& points) :
	points(points)
{
}


void ConvexPolygon::Reverse() {
	for (auto& point : points) {
		point.x = - point.x;
		point.y = - point.y;
	}
}


void ConvexPolygon::CounterClockOrder() {
	auto iterator_of_min_point = std::min_element(points.begin(), points.end(),
		[](const Point& p1, const Point& p2) {
			if (p1.y == p2.y) {
				return (p1.x < p2.x);
			} else {
				return (p1.y < p2.y);
			}
		});
	std::rotate(points.begin(), iterator_of_min_point, points.end());
	std::reverse(points.begin() + 1, points.end());
}


std::vector<Point> ConvexPolygon::GetPoints() const {
	return  points;
}

void ConvexPolygon::Print() const{
	for (const auto& point : points) {
		std::cout<<point.x<<' '<<point.y<<std::endl;
	}
}


bool DoesContainPoint(const ConvexPolygon& polygon, const Point& point) {

	///////////////
	//PROBLEM HERE//
	/////////////

	std::vector<Point> points = polygon.GetPoints();

	Point A = point;
	Point p0 = points[0];
	Point p1 = points[1];
	Point pn = points.back();

	if (A == p0) {
		return true;
	}
	 // в предположении, что порядок сохраняется
	if (IsRightRotation(p0, p1, A) > 0 || IsRightRotation(p0, pn, A) < 0) {
		return false;
	}

	int number = points.size();
	int l = 1, r = number - 1;
	while (r - l > 1) {
		int q = (l + r) / 2;
		if (points[q] == A) {
			return  true;
		}
		double right_rot = IsRightRotation(p0, points[q], A);
		if ( right_rot > 0)
			r = q;
		else
			l = q;
	}
	return !IsIntersectionBetweenEdges( {p0, A}, {points[l], points[r]});			// l!=r
}


double PolarAngle(const Point &p1, const Point &p2) {
	Point vector = p2 - p1;
	Point Ox (1,0);
	double cos = (vector*Ox) / vector.GetModule();
	return ( vector.y >= 0 ) ? std::acos(cos) : 2*M_PI - std::acos(cos);
}


bool ConvexPolygon::BruteForce(const Point &point) const {

	double first_vm = VectorMultiplication((point - points[0]), (points[1] - points[0]));
	int n = points.size();
	bool inside = true;
	if (first_vm == 0) {
		inside = false;
	}
	for (int i = 0; i < points.size(); ++i) {
		if (first_vm * VectorMultiplication((point - points[i]) , (points[(i + 1) % n] - points[i])) < 0  ||
			VectorMultiplication((point - points[i]) , (points[(i + 1) % n] - points[i])) == 0) {
			inside = false;
		}
	}

	bool on_the_border = false;

	for (int i = 0; i < points.size(); ++i) {
		if ( IsPointOnSegment( points[i], points[(i + 1) % n] , point) ) {
			on_the_border = true;
		}
	}
	return (inside || on_the_border);
}



std::vector<Point> MinkSum ( const ConvexPolygon& first, const ConvexPolygon& second ) {

	int i = 0;
	int j = 0;
	std::vector<Point> V = first.GetPoints();
	std::vector<Point> W = second.GetPoints();
	std::vector<Point> answer;
	int n = V.size();
	int m = W.size();
	while (i < n || j < m) {   // do 		// make borders in order to finish building

		Point new_candidate = V[i%n] + W[j%m];
		answer.push_back(new_candidate);

		double V_polar_angle = PolarAngle(V[i%n], V[(i+1)%n]);
		if ( i >= n ) {
			V_polar_angle += 2*M_PI;
		}
		double W_polar_angle = PolarAngle(W[j%m], W[(j+1)%m]);
		if ( j >= m ) {
			W_polar_angle += 2*M_PI;
		}

		if ( V_polar_angle < W_polar_angle) {
			if ( i < n ) {
				++i;
			} else {
				++j;
			}
		}
		else if (V_polar_angle > W_polar_angle ) {
			if ( j < m) {
				++j;
			} else {
				++i;
			}
		}
		else {
			++i;
			++j;
		}
	}
	return answer;
}


//void Cases( const std::vector<Point>& V, const std::vector<Point>& W) {
//
//	int n = V.size();
//	int m = W.size();
//
//	if ( n == 1 && m == 1 ) {												// PointEvent
//		if ( V.front() == W.front() ) {
//			std::cout <<"YES"<<std::endl;
//		} else {
//			std::cout <<"NO"<<std::endl;
//		}
//		exit(0);
//	}
//
//	if ( n == 2 && m == 1 ) { 												// Point - Segment
//		if (IsPointOnSegment(V[0],V[1], W[0])) {
//			std::cout <<"YES"<<std::endl;
//		} else {
//			std::cout <<"NO"<<std::endl;
//		}
//		exit(0);
//	}
//
//	if ( n == 1 && m == 2 ) {												//Segment - Point
//		if (IsPointOnSegment(W[0],W[1], V[0])) {
//			std::cout <<"YES"<<std::endl;
//		} else {
//			std::cout <<"NO"<<std::endl;
//		}
//		exit(0);
//	}
//
//	if ( n == 2 && m == 2 ) {												//Segment - Segment
//		if ( IsIntersectionBetweenEdges({V[0],V[1]},{W[0],W[1]}) ) {
//			std::cout <<"YES"<<std::endl;
//		} else {
//			std::cout <<"NO"<<std::endl;
//		}
//		exit(0);
//	}
//
//	if ( m == 1 && n > 2) {
//		ConvexPolygon polygon(V);
//		if ( DoesContainPoint(polygon, W[0]) ) {
//			std::cout <<"YES"<<std::endl;
//		} else {
//			std::cout <<"NO"<<std::endl;
//		}
//		exit(0);
//	}
//
//	if ( n == 1 && m > 2) {
//		ConvexPolygon polygon(W);
//		if ( DoesContainPoint(polygon, V[0]) ) {
//			std::cout <<"YES"<<std::endl;
//		} else {
//			std::cout <<"NO"<<std::endl;
//		}
//		exit(0);
//	}
//}


void  Input() {

	std::vector<Point> V;
	std::vector<Point> W;

	int n;
	std::cin>>n;
	for (int i = 0; i < n; ++i) {
		int x,y;
		std::cin>>x>>y;
		V.emplace_back(x,y,i);
	}

	int m;
	std::cin>>m;
	for (int i = 0; i < m; ++i) {
		int x,y;
		std::cin>>x>>y;
		W.emplace_back(x,y,i);
	}

//	if( n <= 2 && m <= 2) {
//		Cases(V,W);
//		return;
//	}

	ConvexPolygon first(V);
	ConvexPolygon second(W);

	second.Reverse();
	first.CounterClockOrder();
	second.CounterClockOrder();

	ConvexPolygon MinkSumPolygon( MinkSum( first, second ) );

//	std::cout<<"*********"<<std::endl;
//	MinkSumPolygon.Print();

	Point null_point(0,0);
	if ( MinkSumPolygon.BruteForce(null_point)) {
		std::cout<<"YES"<<std::endl;
	} else {
		std::cout<<"NO"<<std::endl;
	}
}



int main() {

	Input();

	return 0;
}