基本模板

// Code by ajcxsu
// Geometry template

#include<bits/stdc++.h>
#define EPS (1e-9)
using namespace std;

struct Point {
    double x,y;
    Point(double x=0,double y=0):x(x), y(y) {}

    Point operator +(Point p) { return Point(x+p.x,y+p.y); }
    Point operator -(Point p) { return Point(x-p.x,y-p.y); } // 加减
    Point operator *(double a) { return Point(x*a,y*a); }
    Point operator /(double a) { return Point(x/a,y/a); } // 数乘

    double norm() { return x*x+y*y; } // 范数
    double abs() { return sqrt(norm()); } // 大小

    bool operator < (const Point &p) { return x!=p.x?x<p.x:y<p.y; }
    bool operator == (const Point &p) { return fabs(p.x-x) < EPS && fabs(p.y-y) < EPS; }
} ;
typedef Point Vector;

double dot(const Point &a, const Point &b) {
    return a.x*b.x+a.y*b.y;
} // 内积
double cross(const Point &a, const Point &b) {
    return a.x*b.y-a.y*b.x;
} // 外积
bool equals(double a, double b) { return fabs(a-b)<EPS; } // 误差相等

struct Line {
    Point p1,p2;
} ;
typedef Line Seg;

/* 1 正交 2 平行 0 其他 */
int PO(Vector a, Vector b) {
    if(equals(dot(a,b), 0)) return 1;
    else if(equals(cross(a,b), 0)) return 2;
    else return 0;
}
int PO(Line a, Line b) { // 正交、平行判定
    return PO(a.p2-a.p1, b.p2-b.p1);
}

istream& operator >>(istream &in, Vector &a) {
    in>>a.x>>a.y;
    return in;
}
istream& operator >>(istream &in, Line &a) {
    in>>a.p1>>a.p2;
    return in;
} // 输入重载

Point project(Point a, Seg b) {
    Vector base=b.p2-b.p1;
    Vector hypo=a-b.p1;
    return b.p1+base*(dot(base, hypo)/ base.norm());
} // 投影

Point ref(Point a, Seg b) {
    Vector base=project(a,b)-a;
    return a+base*2;
} // 映像

int ccw(Vector a, Vector b) {
    if(cross(a,b)>EPS) return 1; // Counter clockwise
    else if(cross(a,b)<-EPS) return -1; // Clockwise
    else if(dot(a,b)<-EPS) return 2; // Online back
    else if(a.norm()<b.norm()) return -2; // Online front
    else return 0; // On segement
} // 判断顺时针逆时针
int ccw(Point p0, Point p1, Point p2) {
    return ccw(p1-p0, p2-p0);
}

bool intersect(Point p1, Point p2, Point p3, Point p4) {
    if( ccw(p1,p2,p3)*ccw(p1,p2,p4) <= 0 &&
    ccw(p3,p4,p1)*ccw(p3,p4,p2) <= 0) return 1;
    return 0;
}
bool intersect(Seg a, Seg b) {
    return intersect(a.p1, a.p2, b.p1, b.p2);
} // 判断线段是否相交

Point crossp(Seg a, Seg b) {
    Vector base=b.p2-b.p1, hypo=a.p1-b.p1, hypo2=a.p2-b.p1;
    double h1=fabs(cross(base,hypo))/base.abs();
    double h2=fabs(cross(base,hypo2))/base.abs();
    double t=h1/(h1+h2);
    return a.p1+(a.p2-a.p1)*t;
} // 线段交点

double disp(Point a, Seg b) {
    if(dot(b.p2-b.p1,a-b.p1) < 0.0) return (a-b.p1).abs();
    else if(dot(b.p1-b.p2, a-b.p2) < 0.0) return (a-b.p2).abs();
    return (project(a,b)-a).abs();
}
double diss(Seg a, Seg b) {
    if(intersect(a,b)) return 0.0;
    return min(min(disp(a.p1,b), disp(a.p2,b)), min(disp(b.p1,a), disp(b.p2,a)));
}

ostream& operator <<(ostream &out, Vector a) {
    out<<a.x<<' '<<a.y;
    return out;
} // 输出重载

int main() {
    cout.setf(ios::fixed);
    cout<<setprecision(10); // 设置输出精度

    // End of program
    return 0;
}

凸包

// Code by ajcxsu
// Problem: Convex_Hall

#include<bits/stdc++.h>
#define EPS (1e-3)
using namespace std;


struct Point {
    double x,y;
    Point(double x=0.0, double y=0.0):x(x), y(y) {};

    Point operator + (Point b) { return Point(x+b.x, y+b.y); }
    Point operator - (Point b) { return Point(x-b.x, y-b.y); }
    Point operator * (double b) { return Point(x*b, y*b); }

    double norm() { return x*x+y*y; }
    double abs() { return sqrt(norm()); }

    bool operator <(const Point &p) {
        return x!=p.x?x<p.x:y<p.y;
    }
} ;
typedef Point Vector;
typedef vector<Point> Polygon;

double dot(Point a, Point b) { return a.x*b.x+a.y*b.y; }
double cross(Point a, Point b) { return a.x*b.y-a.y*b.x; }

int ccw(Vector a, Vector b) {
    if(cross(a,b)>EPS) return 1;
    if(cross(a,b)<-EPS) return -1;
    return 0;
}
int ccw(Point p0, Point p1, Point p2) {
    return ccw(p1-p0, p2-p0);
}


istream& operator >>(istream &in, Point &x) {
    in>>x.x>>x.y;
    return in;
}
ostream& operator <<(ostream &out, Point x) {
    out<<(int)x.x<<' '<<(int)x.y;
    return out;
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    Point p[100010];
    for(int i=0;i<n;i++) cin>>p[i];

    sort(p,p+n);

    Polygon u,l; // upper lower
    u.push_back(p[0]), u.push_back(p[1]);
    l.push_back(p[n-1]), l.push_back(p[n-2]);

    for(int i=2;i<n;i++) {
        for(int n=u.size(); n>=2 && ccw(u[n-2], u[n-1], p[i])>0; n--) u.pop_back(); // 这里变量混用了..见谅
        u.push_back(p[i]);
    }
    for(int i=n-3;i>=0;i--) {
        for(int n=l.size(); n>=2 && ccw(l[n-2], l[n-1], p[i])>0; n--) l.pop_back();
        l.push_back(p[i]);
    }
    /* 以下皆为输出格式处理 */
    reverse(l.begin(),l.end());
    for(int i=u.size()-2;i>=1;i--) l.push_back(u[i]);
    cout<<l.size()<<endl;
    int sta=0;
    for(int i=1, n=l.size();i<n;i++) {
        if(l[i].y<l[sta].y) sta=i;
        else if(l[i].y==l[sta].y && l[i].x<l[sta].x) sta=i;
    }
    cout<<l[sta]<<endl;
    for(int i=(sta+1)%l.size(), n=l.size(); i!=sta;i=(i+1)%n) {
        cout<<l[i]<<endl;
    }
    return 0;
}

内包

// Code by ajcxsu
// Problem: contain

#include<bits/stdc++.h>
using namespace std;

struct P {
    double x,y;
    P (double x=0.0, double y=0.0):x(x),y(y) {}

    P operator + (const P &b) { return P(x+b.x, y+b.y); }
    P operator - (const P &b) { return P(x-b.x, y-b.y); }

    double norm() { return x*x+y*y; }
    double abs() { return sqrt(norm()); }
} ;
typedef P Vector;

double dot(P x, P y) { return x.x*y.x+x.y*y.y; }
double cross(P a, P b) { return a.x*b.y-a.y*b.x; }

typedef vector<P> Polygon;

istream& operator >>(istream &in, P &a) {
    in>>a.x>>a.y;
    return in;
}

ostream& operator <<(ostream &out, P a) {
    out<<a.x<<' '<<a.y;
    return out;
}
#define EPS 1e-9

int contain(P x, Polygon &S) {
    bool res=0;
    for(int i=1, len=S.size(); i<len;i++) {
        Vector a=S[i-1]-x, b=S[i]-x;
        if(fabs(cross(a,b))<EPS && dot(a,b)<EPS) return 1;
        if(a.y>b.y) swap(a,b);
        if(a.y<EPS && b.y>EPS && cross(a,b)>EPS) res=!res;
    }
    return res?2:0;
}

Polygon S;
int n;

int main() {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout<<setprecision(10);
    cin>>n;
    P na;
    for(int i=0;i<n;i++) cin>>na,S.push_back(na);
    S.push_back(S[0]);
    int q;
    cin>>q;
    while(q--) {
        cin>>na;
        cout<<contain(na,S)<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/ji-suan-ji-he.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆