向量
<pre><code class="language-cpp">#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int maxn = 1e5+6;
int sgn(double x){
if(fabs(x) < eps) return 0;
if(x < 0) return -1;
else return 1;
}
struct Point{
double x, y;
Point(double _x = 0, double _y = 0){
x = _x;
y = _y;
}
};
//两点距离
double distance(Point p1,Point p2){
return sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y));
}
typedef Point Vector;
//向量相加 A+B
Vector operator+(Vector A, Vector B){
return Vector(A.x + B.x, A.y + B.y);
}
//向量相加 A-B
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);
}
//向量点乘
double operator*(Vector A, Vector B){
return A.x * B.x + A.y * B.y;
}
//向量差乘的长度
double operator^(Vector A, Vector B){
return A.x * B.y - A.y * B.x;
}
//向量/数
Vector operator/(Vector A, double p){
return Vector(A.x / p, A.y / p);
}
//向量长度平方
double length2(const Vector &A){
return A.x * A.x + A.y * A.y;
}
//向量长度
double length(const Vector &A){
return sqrt(A.x * A.x + A.y * A.y);
}
bool cmp1(const Point &A,const Point &B) {
return sgn(A.y - B.y) < 0 || ((sgn(A.y-B.y) == 0 && sgn(A.x-B.x) < 0));
}
//极角排序,角度相同的则距离小的在前面
bool cmp2(const Point &A, const Point &B){
return sgn(A ^ B) > 0 || (sgn(A ^ B) == 0 && sgn(length(A) - length(B)) < 0);
}
struct Line{
Point a, b;
Line(Point _a = Point(0, 0), Point _b = Point(0, 0)){
a = _a;
b = _b;
}
};
//两直线交点（前提是平行）
Point intersection(Line u, Line v){
Point ret = u.a;
double t = ((u.a.x-v.a.x)*(v.a.y-v.b.y) - (u.a.y-v.a.y)*(v.a.x-v.b.x))
/((u.a.x-u.b.x)*(v.a.y-v.b.y) - (u.a.y-u.b.y)*(v.a.x-v.b.x));
ret.x += (u.b.x-u.a.x) * t;
ret.y += (u.b.y-u.a.y) * t;
return ret;
}
//判断点是否在直线上
bool online(Point p, Line l){
return !sgn((p-l.a) ^ (p-l.b)) && sgn((p-l.a) * (p-l.b)) < 0;
}
typedef Line Segment;
typedef vector<Point> Poly;
//求出多边形 lst的凸包，放在ans里面
void graham(Poly &lst, Poly &ans){
sort(lst.begin(), lst.end(), cmp1);
Point bs = lst[0];
static vector<int> stk;
stk.clear();
stk.push_back(0);
for(int i = 0; i < lst.size(); i++) lst[i] = lst[i] - bs;
Poly::iterator p = lst.begin(); p++;
sort(p, lst.end(), cmp2);//极角排序
for(int i = 1; i < lst.size(); i++){
while(stk.size() > 1
&& sgn((lst[i]-lst[stk[stk.size()-2]]) ^ (lst[stk.back()]-lst[stk[stk.size()-2]])) >= 0)
stk.pop_back();
stk.push_back(i);
}
for(int i = 0; i < stk.size(); i++)
ans.push_back(lst[stk[i]] + bs);
return;
}
//求出多边形A和B的闵可夫斯基和，放在ans里面
void minkowski(Poly &A, Poly &B, Poly &ans){ //求闵可夫斯基和
static Poly v1, v2;
v1.clear(), v2.clear();
for(int i = 0; i < A.size()-1; i++) v1.push_back(A[i+1] - A[i]);
for(int i = 0; i < B.size()-1; i++) v2.push_back(B[i+1] - B[i]);
v1.push_back(A[0] - A.back()), v2.push_back(B[0] - B.back());
ans.push_back(A[0] + B[0]);
int p1 = 0, p2 = 0;
while(p1 < v1.size() && p2 < v2.size()){
if(sgn(v1[p1] ^ v2[p2]) >= 0) ans.push_back(ans.back() + v1[p1++]);
else ans.push_back(ans.back() + v2[p2++]);
}
while(p1 < v1.size()) ans.push_back(ans.back() + v1[p1++]);
while(p2 < v2.size()) ans.push_back(ans.back() + v2[p2++]);
}
//判断点在多边形内（凸包内）
bool in(Poly &P, Point a){
if(sgn((a-P[0]) ^ (P[1]-P[0])) > 0 || sgn((P.back()-P[0]) ^ (a-P[0])) > 0)
return false;
if(online(a, Line(P[0], P[1])) || online(a, Line(P[0], P.back())))
return true;
int l = 1, r = P.size()-2;
while(l < r){
int mid= (l+r+1) >> 1;
if(sgn((a-P[0]) ^ (P[mid]-P[0])) > 0) r = mid - 1;
else l=mid;
}
return sgn((a-P[r]) ^ (P[r+1]-P[r])) <= 0;
}
Poly A, B, AA, BB;
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++){
Point a;
scanf("%lf%lf",&a.x,&a.y);
A.push_back(a);
}
graham(A, AA);
for(int i=1;i<=m;i++){
Point a;
scanf("%lf%lf",&a.x,&a.y);
a.x=-a.x;
a.y=-a.y;
B.push_back(a);
}
graham(B, BB);
A = AA, B = BB;
// for(int i = 0; i < BB.size(); i++) cout << "(" << BB[i].x << " " << BB[i].y << ")" << endl;
AA.clear(); BB.clear();
minkowski(A,B,AA);
graham(AA, BB);
while(q--){
Point t;
scanf("%lf%lf",&t.x,&t.y);
printf("%d\n",in(BB,t));
}
return 0;
}
</code></pre>