http://codeforces.com/gym/101484/problem/E
题解 凸包板题
#define _CRT_SECURE_NO_WARNINGS
#include<cmath>
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define rep(i,t,n) for(int i =(t);i<=(n);++i)
#define per(i,n,t) for(int i =(n);i>=(t);--i)
#define mmm(a,b) memset(a,b,sizeof(a)) const int maxn = 2e5 + ;
int a[maxn];
typedef long long ll;
const double eps = 1e-;//eps用于控制精度
struct Point//点或向量
{
double x, y;
Point() {}
Point(double x, double y) :x(x), y(y) {}
};
bool cmp1(Point a,Point b){
if(a.x==b.x)return a.y<b.y;
else return a.x<b.x;
}
struct triVec {
double x, y,z;
triVec() {}
triVec(double x, double y,double z) :x(x), y(y),z(z) {}
};
typedef Point Vector;
Vector operator + (Vector a, Vector b)//向量加法
{
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator - (Vector a, Vector b)//向量减法
{
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator * (Vector a, double p)//向量数乘
{
return Vector(a.x*p, a.y*p);
}
Vector operator / (Vector a, double p)//向量数除
{
return Vector(a.x / p, a.y / p);
}
int dcmp(double x)//精度三态函数(>0,<0,=0)
{
if (fabs(x) < eps)return ;
else if (x > )return ;
return -;
}
bool operator == (const Point &a, const Point &b)//向量相等
{
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
}
double Dot(Vector a, Vector b)//内积
{
return a.x*b.x + a.y*b.y;
}
double Length(Vector a)//模
{
return sqrt(Dot(a, a));
}
Vector Rotate(Vector a, double rad)//逆时针旋转
{
return Vector(a.x*cos(rad) - a.y*sin(rad), a.x*sin(rad) + a.y*cos(rad));
}
double Cross(Vector a, Vector b)//外积
{
return a.x*b.y - a.y*b.x;
}
double Distance(Point a, Point b)//两点间距离
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
int n, m;
double z;
//Point p[maxn]; Point f1[maxn];
Point f2[maxn];
Point result[maxn];
vector<Point> P;
int top;
bool cmp(Point A, Point B)
{
double ans = Cross(A - P[], B - P[]);
if (dcmp(ans) == )
return dcmp(Distance(P[], A) - Distance(P[], B)) < ;
else
return ans > ;
}
void Graham()//Graham凸包扫描算法
{
for (int i = ; i < P.size(); i++)//寻找起点
if (P[i].y < P[].y || (dcmp(P[i].y - P[].y) == && P[i].x < P[].x))
swap(P[i], P[]);
sort(P.begin()+, P.end(), cmp);//极角排序，中心为起点
result[] = P[];
result[] = P[];
top = ;
for (int i = ; i < P.size(); i++)
{
while (Cross(result[top] - result[top - ], P[i] - result[top - ]) < && top >= )
top--;
result[++top] = P[i];
}
} int main() {
int n,m;
cin>>n>>m;
rep(i,,n){scanf("%lf%lf",&f1[i].x,&f1[i].y);P.push_back(f1[i]);}
rep(i,,m){scanf("%lf%lf",&f2[i].x,&f2[i].y);P.push_back(f2[i]);}
//if(n<=2||m<=2) return 0*printf("NO\n");
Graham();
sort(result,result+top,cmp);
sort(f1+,f1+n+,cmp);
sort(f2+,f2+n+,cmp);
int f=,ff=;
rep(i,,n){
if(!(f1[i]==result[i-]))f=; }
if(n!=top+)f=;
rep(i,,m){
if(!(f2[i]==result[i-]))ff=;
}
if(m!=top+)f=;
/* rep(i,1,n)cout<<f1[i].x<<'*'<<f1[i].y<<' ';
cout<<endl;
rep(i,1,m)cout<<f2[i].x<<'*'<<f2[i].y<<' ';
cout<<endl;
rep(i,0,top)cout<<result[i].x<<'*'<<result[i].y<<' ';
cout<<endl;*/
if(f|ff)puts("YES");
else puts("NO"); }