Problem Link : http://codeforces.com/gym/101484/problem/E
Solution Idea:
-
Let P1 and P2 be respectively the set of points of the first polygon and the set of points of the second polygon. Let ch(X) be the set of points on the convex hull of the set of points X, including colinear points on the edges. A polygon is strictly inside the other if ch(P1 U P2 equals to P1 or P2.
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<iostream>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<climits>
#include<complex>
#define mp make_pair
#define pb push_back
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const double inf=1e20;
const int maxp=200007;
int dblcmp(double d)
{
if (fabs(d)<eps)return 0;
return d>eps?1:-1;
}
inline double sqr(double x)
{
return x*x;
}
struct point
{
double x,y;
point() { }
point(double _x,double _y)
{
x = _x;
y = _y;
}
void input()
{
scanf("%lf%lf",&x,&y);
}
void output()
{
printf("%.2f %.2f\n",x,y);
}
bool operator==(point a)const
{
return dblcmp(a.x - x) == 0 && dblcmp(a.y - y) == 0;
}
bool operator<(point a)const
{
return dblcmp(a.x - x) == 0 ? dblcmp(y - a.y) < 0 : x < a.x;
}
point operator-(point a)const
{
return point(x-a.x, y-a.y);
}
double len()
{
return hypot(x, y);
}
double len2()
{
return x * x + y * y;
}
double distance(point p)
{
return hypot(x - p.x, y - p.y);
}
point add(point p)
{
return point(x + p.x, y + p.y);
}
point sub(point p)
{
return point(x - p.x, y - p.y);
}
point mul(double b)
{
return point(x * b, y * b);
}
point div(double b)
{
return point(x / b, y / b);
}
double dot(point p)
{
return x*p.x+y*p.y;
}
double det(point p)
{
return x*p.y-y*p.x;
}
double rad(point a,point b)
{
point p=*this;
return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p))));
}
point trunc(double r)
{
double l=len();
if (!dblcmp(l))return *this;
r/=l;
return point(x*r,y*r);
}
point rotleft()
{
return point(-y,x);
}
point rotright()
{
return point(y,-x);
}
point rotate(point p,double angle)
{
point v=this->sub(p);
double c=cos(angle),s=sin(angle);
return point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
}
};
struct line
{
point a,b;
line() { }
line(point _a,point _b)
{
a=_a;
b=_b;
}
bool operator==(line v)
{
return (a==v.a)&&(b==v.b);
}
line(point p,double angle)
{
a=p;
if (dblcmp(angle-pi/2)==0)
{
b=a.add(point(0,1));
}
else
{
b=a.add(point(1,tan(angle)));
}
}
//ax+by+c=0
line(double _a,double _b,double _c)
{
if (dblcmp(_a)==0)
{
a=point(0,-_c/_b);
b=point(1,-_c/_b);
}
else if (dblcmp(_b)==0)
{
a=point(-_c/_a,0);
b=point(-_c/_a,1);
}
else
{
a=point(0,-_c/_b);
b=point(1,(-_c-_a)/_b);
}
}
void input()
{
a.input();
b.input();
}
void adjust()
{
if(b<a)swap(a,b);
}
double length()
{
return a.distance(b);
}
double angle()
{
double k=atan2(b.y-a.y,b.x-a.x);
if (dblcmp(k)<0)k+=pi;
if (dblcmp(k-pi)==0)k-=pi;
return k;
}
int relation(point p)
{
int c=dblcmp(p.sub(a).det(b.sub(a)));
if (c<0)return 2;
if (c>0)return 1;
return 0;
}
bool pointonseg(point p)
{
return dblcmp(p.sub(a).det(b.sub(a)))==0&&dblcmp(p.sub(a).dot(p.sub(b)))<=0;
}
bool parallel(line v)
{
return dblcmp(b.sub(a).det(v.b.sub(v.a)))==0;
}
int segcrossseg(line v)
{
int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
if ((d1^d2)==-2&&(d3^d4)==-2)return 2;
return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||
d2==0&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=0||
d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||
d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);
}
int segcrossseg_inside(line v)
{
if(v.pointonseg(a) || v.pointonseg(b) || pointonseg(v.a) || pointonseg(v.b)) return 0;
int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
if ((d1^d2)==-2&&(d3^d4)==-2)return 1;
return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||
d2==0&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=0||
d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||
d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);
}
int linecrossseg(line v) //*this seg v line
{
int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
if ((d1^d2)==-2)return 2;
return (d1==0||d2==0);
}
int linecrossline(line v)
{
if ((*this).parallel(v))
{
return v.relation(a)==3;
}
return 2;
}
point crosspoint(line v)
{
double a1=v.b.sub(v.a).det(a.sub(v.a));
double a2=v.b.sub(v.a).det(b.sub(v.a));
return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));
}
double dispointtoline(point p)
{
return fabs(p.sub(a).det(b.sub(a)))/length();
}
double dispointtoseg(point p)
{
if (dblcmp(p.sub(b).dot(a.sub(b)))<0||dblcmp(p.sub(a).dot(b.sub(a)))<0)
{
return min(p.distance(a),p.distance(b));
}
return dispointtoline(p);
}
point lineprog(point p)
{
return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a))/b.sub(a).len2()));
}
point symmetrypoint(point p)
{
point q=lineprog(p);
return point(2*q.x-p.x,2*q.y-p.y);
}
};
struct polygon
{
int n=0;
point p[maxp];
line l[maxp];
void input(int _n)
{
n=_n;
for (int i=0; i<n; i++) p[i].input();
}
void add(point q)
{
p[n++]=q;
}
void getline()
{
for (int i=0; i<n; i++)
l[i]=line(p[i],p[(i+1)%n]);
}
struct cmp
{
point p;
cmp(const point &p0)
{
p=p0;
}
bool operator()(const point &aa,const point &bb)
{
point a=aa,b=bb;
int d=dblcmp(a.sub(p).det(b.sub(p)));
if (d==0)
return dblcmp(a.distance(p)-b.distance(p))<0;
return d>0;
}
};
void norm()
{
point mi=p[0];
for (int i=1; i<n; i++)mi=min(mi,p[i]);
sort(p,p+n,cmp(mi));
}
void getconvex(polygon &convex)
{
int i;
sort(p,p+n);
convex.n=n;
for (i=0; i<min(n,2); i++) convex.p[i]=p[i];
if (n<=2)return;
int &top=convex.n;
top=1;
for (i=2; i<n; i++)
{
while (top&&convex.p[top].sub(p[i]).det(convex.p[top-1].sub(p[i]))<0)
top--;
convex.p[++top]=p[i];
}
int temp=top;
convex.p[++top]=p[n-2];
for (i=n-3; i>=0; i--)
{
while (top!=temp&&convex.p[top].sub(p[i]).det(convex.p[top-1].sub(p[i]))<0)
top--;
convex.p[++top]=p[i];
}
}
bool isconvex()
{
bool s[3];
memset(s,0,sizeof(s));
int i,j,k;
for (i=0; i<n; i++)
{
j=(i+1)%n;
k=(j+1)%n;
s[dblcmp(p[j].sub(p[i]).det(p[k].sub(p[i])))+1]=1;
if (s[0]&&s[2])return 0;
}
return 1;
}
};
int main()
{
int n,m;
scanf("%d %d",&n,&m);
polygon a,b,ab;
for(int i=0; i<n; i++)
{
double x,y;
scanf("%lf %lf",&x,&y);
a.add(point(x,y));
ab.add(point(x,y));
}
for(int i=0; i<m; i++)
{
double x,y;
scanf("%lf %lf",&x,&y);
b.add(point(x,y));
ab.add(point(x,y));
}
polygon cha, chb, chab;
// a.getconvex(cha);
// b.getconvex(chb);
ab.getconvex(chab);
sort(a.p,a.p+a.n);
sort(b.p,b.p+b.n);
sort(chab.p,chab.p+chab.n);
// cout<<ab.n<<endl;
// for(int i=0;i<ab.n;i++)
// cout<<ab.p[i].x<<" "<<ab.p[i].y<<endl;
//
// cout<<"---------------------"<<endl;
//
// cout<<chab.n<<endl;
// for(int i=0;i<chab.n;i++)
// cout<<chab.p[i].x<<" "<<chab.p[i].y<<endl;
if(a.n==chab.n)
{
bool check=0;
for(int i=0; i<a.n; i++)
if(a.p[i]==chab.p[i]) continue;
else
{
check=1;
break;
}
if(check==0)
{
printf("YES\n");
return 0;
}
}
if(b.n==chab.n)
{
bool check=0;
for(int i=0; i<b.n; i++)
if(b.p[i]==chab.p[i]) continue;
else
{
check=1;
break;
}
if(check==0)
{
printf("YES\n");
return 0;
}
}
printf("NO\n");
return 0;
}