登录
← 返回首页 | 代码片段 › 8 计算几何 › 8.3 计算几何综合 › 计算几何综合 / 搜索
JSON MD

8.3 计算几何综合

计算几何大板子 Geometry
293 行
CPP JSON
【计算几何大板子(Computational Geometry Library)】 ▪ eq(x, y) — 浮点/整数判等(abs(x-y)≤eps) ▪ type(x, y) — 判断点 (x,y) 所在象限(用于极角排序) ▪ Point — 二维点/向量结构(模板类型 T,默认 long long 支持整数几何): — +、-、*(点积)、*=(标量乘)运算符重载 — cross(r) — 叉积 x*ry - y*rx(判断方向、面积) — toleft(r) — 判断 r 在当前向量左侧(1)/同向(0)/右侧(-1) — arg_cmp(r) — 极角比较器(按象限+叉积排序) — operator< — 按 (x,y) 字典序比较 ▪ Line — 线段/直线结构 ▪ operator<< / operator>> — 输入输出流重载 使用整数几何避免浮点精度问题。适用于凸包、线段相交、点在多边形内判定、最近点对等。
C++ 293 行 CPP
namespace Geometry {
using T = ll;
constexpr T eps = 0;

bool eq(const T &x, const T &y) { return abs(x - y) <= eps; }
inline constexpr int type(T x, T y) {
    if(x == 0 and y == 0) return 0;
    if(y < 0 or (y == 0 and x > 0)) return -1;
    return 1;
}
struct Point {
    T x, y;
    constexpr Point(T _x = 0, T _y = 0) : x(_x), y(_y) {}
    constexpr Point operator+() const noexcept { return *this; }
    constexpr Point operator-() const noexcept { return Point(-x, -y); }
    constexpr Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
    constexpr Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }
    constexpr Point &operator+=(const Point &p) { return x += p.x, y += p.y, *this; }
    constexpr Point &operator-=(const Point &p) { return x -= p.x, y -= p.y, *this; }
    constexpr T operator*(const Point &p) const { return x * p.x + y * p.y; }
    constexpr Point &operator*=(const T &k) { return x *= k, y *= k, *this; }
    constexpr Point operator*(const T &k) { return Point(x * k, y * k); }
    constexpr bool operator==(const Point &r) const noexcept { return r.x == x and r.y == y; }
    constexpr T cross(const Point &r) const { return x * r.y - y * r.x; }

    constexpr bool operator<(const Point &r) const { return pair(x, y) < pair(r.x, r.y); }

    // 1 : left, 0 : same, -1 : right
    constexpr int toleft(const Point &r) const {
        auto t = cross(r);
        return t > eps ? 1 : t < -eps ? -1 : 0;
    }

    constexpr bool arg_cmp(const Point &r) const {
        int L = type(x, y), R = type(r.x, r.y);
        if(L != R) return L < R;

        T X = x * r.y, Y = r.x * y;
        if(X != Y) return X > Y;
        return x < r.x;
    }
};
bool arg_cmp(const Point &l, const Point &r) { return l.arg_cmp(r); }
ostream &operator<<(ostream &os, const Point &p) { return os << p.x << " " << p.y; }
istream &operator>>(istream &is, Point &p) {
    is >> p.x >> p.y;
    return is;
}

struct Line {
    Point a, b;
    Line() = default;
    Line(Point a, Point b) : a(a), b(b) {}
    // ax + by = c
    Line(T A, T B, T C) {
        if(A == 0) {
            a = Point(0, C / B), b = Point(1, C / B);
        } else if(B == 0) {
            a = Point(C / A, 0), b = Point(C / A, 1);
        } else {
            a = Point(0, C / B), b = Point(C / A, 0);
        }
    }
    // 1 : left, 0 : same, -1 : right
    constexpr int toleft(const Point &r) const {
        auto t = (b - a).cross(r - a);
        return t > eps ? 1 : t < -eps ? -1 : 0;
    }

    friend std::ostream &operator<<(std::ostream &os, Line &ls) {
        return os << "{"
                  << "(" << ls.a.x << ", " << ls.a.y << "), (" << ls.b.x << ", " << ls.b.y << ")}";
    }
};
istream &operator>>(istream &is, Line &p) { return is >> p.a >> p.b; }

struct Segment : Line {
    Segment() = default;
    Segment(Point a, Point b) : Line(a, b) {}
};

ostream &operator<<(ostream &os, Segment &p) { return os << p.a << " to " << p.b; }
istream &operator>>(istream &is, Segment &p) {
    is >> p.a >> p.b;
    return is;
}

struct Circle {
    Point p;
    T r;
    Circle() = default;
    Circle(Point p, T r) : p(p), r(r) {}
};

using pt = Point;
using Points = vector<pt>;
using Polygon = Points;
T cross(const pt &x, const pt &y) { return x.x * y.y - x.y * y.x; }
T dot(const pt &x, const pt &y) { return x.x * y.x + x.y * y.y; }

T abs2(const pt &x) { return dot(x, x); }
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C
// 点の回転方向
int ccw(const Point &a, Point b, Point c) {
    b = b - a, c = c - a;
    if(cross(b, c) > 0) return +1;   // "COUNTER_CLOCKWISE"
    if(cross(b, c) < 0) return -1;   // "CLOCKWISE"
    if(dot(b, c) < 0) return +2;     // "ONLINE_BACK"
    if(abs2(b) < abs2(c)) return -2; // "ONLINE_FRONT"
    return 0;                        // "ON_SEGMENT"
}

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A
// 平行判定
bool parallel(const Line &a, const Line &b) { return (cross(a.b - a.a, b.b - b.a) == 0); }

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A
// 垂直判定
bool orthogonal(const Line &a, const Line &b) { return (dot(a.a - a.b, b.a - b.b) == 0); }

bool intersect(const Line &l, const Point &p) { return abs(ccw(l.a, l.b, p)) != 1; }

bool intersect(const Line &l, const Line &m) { return !parallel(l, m); }

bool intersect(const Segment &s, const Point &p) { return ccw(s.a, s.b, p) == 0; }

bool intersect(const Line &l, const Segment &s) { return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) <= 0; }

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B
bool intersect(const Segment &s, const Segment &t) { return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0; }

bool intersect(const Polygon &ps, const Polygon &qs) {
    int pl = si(ps), ql = si(qs), i = 0, j = 0;
    while((i < pl or j < ql) and (i < 2 * pl) and (j < 2 * ql)) {
        auto ps0 = ps[(i + pl - 1) % pl], ps1 = ps[i % pl];
        auto qs0 = qs[(j + ql - 1) % ql], qs1 = qs[j % ql];
        if(intersect(Segment(ps0, ps1), Segment(qs0, qs1))) return true;
        Point a = ps1 - ps0;
        Point b = qs1 - qs0;
        T v = cross(a, b);
        T va = cross(qs1 - qs0, ps1 - qs0);
        T vb = cross(ps1 - ps0, qs1 - ps0);

        if(!v and va < 0 and vb < 0) return false;
        if(!v and !va and !vb) {
            i += 1;
        } else if(v >= 0) {
            if(vb > 0)
                i += 1;
            else
                j += 1;
        } else {
            if(va > 0)
                j += 1;
            else
                i += 1;
        }
    }
    return false;
}

T norm(const Point &p) { return p.x * p.x + p.y * p.y; }
Point projection(const Segment &l, const Point &p) {
    T t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
    return l.a + (l.a - l.b) * t;
}

Point crosspoint(const Line &l, const Line &m) {
    T A = cross(l.b - l.a, m.b - m.a);
    T B = cross(l.b - l.a, l.b - m.a);
    if(A == 0 and B == 0) return m.a;
    return m.a + (m.b - m.a) * (B / A);
}

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C
Point crosspoint(const Segment &l, const Segment &m) { return crosspoint(Line(l), Line(m)); }

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_B
// 凸性判定
bool is_convex(const Points &p) {
    int n = (int)p.size();
    for(int i = 0; i < n; i++) {
        if(ccw(p[(i + n - 1) % n], p[i], p[(i + 1) % n]) == -1) return false;
    }
    return true;
}

Points convex_hull(Points p) {
    int n = p.size(), k = 0;
    if(n <= 2) return p;
    sort(begin(p), end(p), [](pt x, pt y) { return (x.x != y.x ? x.x < y.x : x.y < y.y); });
    Points ch(2 * n);
    for(int i = 0; i < n; ch[k++] = p[i++]) {
        while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0) --k;
    }
    for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
        while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0) --k;
    }
    ch.resize(k - 1);
    return ch;
}

// 面積の 2 倍
T area2(const Points &p) {
    T res = 0;
    rep(i, si(p)) { res += cross(p[i], p[i == si(p) - 1 ? 0 : i + 1]); }
    return res;
}

enum { _OUT, _ON, _IN };

int contains(const Polygon &Q, const Point &p) {
    bool in = false;
    for(int i = 0; i < Q.size(); i++) {
        Point a = Q[i] - p, b = Q[(i + 1) % Q.size()] - p;
        if(a.y > b.y) swap(a, b);
        if(a.y <= 0 && 0 < b.y && cross(a, b) < 0) in = !in;
        if(cross(a, b) == 0 && dot(a, b) <= 0) return _ON;
    }
    return in ? _IN : _OUT;
}

Polygon Minkowski_sum(const Polygon &P, const Polygon &Q) {
    vector<Segment> e1(P.size()), e2(Q.size()), ed(P.size() + Q.size());
    const auto cmp = [](const Segment &u, const Segment &v) { return (u.b - u.a).arg_cmp(v.b - v.a); };
    rep(i, P.size()) e1[i] = {P[i], P[(i + 1) % P.size()]};
    rep(i, Q.size()) e2[i] = {Q[i], Q[(i + 1) % Q.size()]};
    rotate(begin(e1), min_element(all(e1), cmp), end(e1));
    rotate(begin(e2), min_element(all(e2), cmp), end(e2));
    merge(all(e1), all(e2), begin(ed), cmp);
    const auto check = [](const Points &res, const Point &u) {
        const auto back1 = res.back(), back2 = *prev(end(res), 2);
        return eq(cross(back1 - back2, u - back2), eps) and dot(back1 - back2, u - back1) >= -eps;
    };
    auto u = e1[0].a + e2[0].a;
    Points res{u};
    res.reserve(P.size() + Q.size());
    for(const auto &v : ed) {
        u = u + v.b - v.a;
        while(si(res) >= 2 and check(res, u)) res.pop_back();
        res.eb(u);
    }
    if(res.size() and check(res, res[0])) res.pop_back();
    return res;
}

// -1 : on, 0 : out, 1 : in
// O(log(n))
int is_in(const Polygon &p, const Point &a) {
    if(p.size() == 1) return a == p[0] ? -1 : 0;
    if(p.size() == 2) return intersect(Segment(p[0], p[1]), a);
    if(a == p[0]) return -1;
    if((p[1] - p[0]).toleft(a - p[0]) == -1 || (p.back() - p[0]).toleft(a - p[0]) == 1) return 0;
    const auto cmp = [&](const Point &u, const Point &v) { return (u - p[0]).toleft(v - p[0]) == 1; };
    const size_t i = lower_bound(p.begin() + 1, p.end(), a, cmp) - p.begin();
    if(i == 1) return intersect(Segment(p[0], p[i]), a) ? -1 : 0;
    if(i == p.size() - 1 && intersect(Segment(p[0], p[i]), a)) return -1;
    if(intersect(Segment(p[i - 1], p[i]), a)) return -1;
    return (p[i] - p[i - 1]).toleft(a - p[i - 1]) > 0;
}

Points halfplane_intersection(vector<Line> L, const T inf = 1e9) {
    Point box[4] = {Point(inf, inf), Point(-inf, inf), Point(-inf, -inf), Point(inf, -inf)};
    rep(i, 4) { L.emplace_back(box[i], box[(i + 1) % 4]); }
    sort(all(L), [](const Line &l, const Line &r) { return (l.b - l.a).arg_cmp(r.b - r.a); });
    deque<Line> dq;
    int len = 0;
    auto check = [](const Line &a, const Line &b, const Line &c) { return a.toleft(crosspoint(b, c)) == -1; };
    rep(i, L.size()) {
        while(dq.size() > 1 and check(L[i], *(end(dq) - 2), *(end(dq) - 1))) dq.pop_back();
        while(dq.size() > 1 and check(L[i], dq[0], dq[1])) dq.pop_front();
        // dump(L[i], si(dq));

        if(dq.size() and eq(cross(L[i].b - L[i].a, dq.back().b - dq.back().a), 0)) {
            if(dot(L[i].b - L[i].a, dq.back().b - dq.back().a) < eps) return {};
            if(L[i].toleft(dq.back().a) == -1)
                dq.pop_back();
            else
                continue;
        }
        dq.emplace_back(L[i]);
    }

    while(dq.size() > 2 and check(dq[0], *(end(dq) - 2), *(end(dq) - 1))) dq.pop_back();
    while(dq.size() > 2 and check(dq.back(), dq[0], dq[1])) dq.pop_front();
    if(si(dq) < 3) return {};
    Polygon ret(dq.size());
    rep(i, dq.size()) ret[i] = crosspoint(dq[i], dq[(i + 1) % dq.size()]);
    return ret;
}
} // namespace Geometry

using namespace Geometry;
求凸包直径(旋转卡壳) tubao
158 行
CPP JSON
【求凸包直径(旋转卡壳)(tubao)】 旋转卡壳(Rotating Calipers)模板,求凸包直径/最远点对。 核心函数: int gcd(int x,int y) — 最大公约数 int ksm(int a,int n,int p) — 核心算法函数 int sgn(double x) — SG函数计算 double cross(const Point& a, const Point& b) — 叉积运算 double cross(const Point& p0, const Point& p1, const Point& p2) — 叉积运算 int dist(const Point& p0, const Point& p1) — 计算距离 vector<Point> convex_hull(vector<Point>& P) — 求凸包 int hull_diam(vector<Point>& hull) — 核心算法函数 核心结构体:Point 关键配置: N=1e6+5,mod=998244353,inf=1e9+7,eps=1e-9 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 158 行 CPP
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // 包含所有容器(哈希表、树、堆)
#include <ext/pb_ds/tree_policy.hpp>     // 包含树的相关策略(用于实现平衡树)
#include <ext/pb_ds/hash_policy.hpp>     // 包含哈希表的相关策略
//#include <ext/pb_ds/priority_queue.hpp>  // 包含优先级队列(堆)
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define up(i, a, b) for (int i = (a); i <= (b); ++i)
#define down(i, a, b) for (int i = (a); i >= (b); --i)
#define sm int,vector<int>,greater<int>
#define int long long
mt19937_64 gen(12345);
const int N=1e6+5,mod=998244353,inf=1e9+7;;
int n,m,q,k;
int a[N],b[N],c[N],d[N];
int gcd(int x,int y)
{
	if(y==0)return x;
	return gcd(y,x%y);
}
int ksm(int a,int n,int p)
{
	if(n<0)return 0;
	int res=1;
	while(n)
	{
		if(n&1)res=res*a%p;
		n>>=1;
		a=a*a%p;
	}
	return res;
}
const double eps = 1e-9;
int sgn(double x) {
	if (abs(x) < eps) return 0;
	return x < 0 ? -1 : 1;
}
struct Point {
	double x, y;
	Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
	
	Point operator - (const Point& b) const {
		return Point(x - b.x, y - b.y);
	}
	
	//优先按 x 排序,x 相同按 y 排序
	bool operator < (const Point& b) const {
		if (sgn(x - b.x) == 0) return sgn(y - b.y) < 0;
		return sgn(x - b.x) < 0;
	}
	
	// 判等(用于去重)
	bool operator == (const Point& b) const {
		return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
	}
};

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

// 返回值 > 0:p2 在 p0->p1 的左侧(向左转)
// 返回值 < 0:p2 在 p0->p1 的右侧(向右转)
// 返回值 == 0:三点共线
double cross(const Point& p0, const Point& p1, const Point& p2) {
	return cross(p1 - p0, p2 - p0);
}

int dist(const Point& p0, const Point& p1){
	return (p0.x-p1.x)*(p0.x-p1.x)+(p0.y-p1.y)*(p0.y-p1.y);
}
// 输入点集 P,返回凸包上的点集(逆时针顺序,起点和终点不重合)
vector<Point> convex_hull(vector<Point>& P) {
	int n = P.size();
	if (n <= 2) return P; // 退化情况:点数小于等于2,本身就是凸包
	
	// 1. 排序并去重
	sort(P.begin(), P.end());
	P.erase(unique(P.begin(), P.end()), P.end());
	n = P.size();
	if (n <= 2) return P;
	
	vector<Point> hull(2 * n); // 用数组模拟栈,速度最快
	int top = 0;               // 栈顶指针,表示栈内元素个数
	
	// 2. 求下凸壳
	for (int i = 0; i < n; i++) {
		// 【核心判断】:如果向右转或共线,则弹栈
		// 注意:如果你需要保留凸包边上的共线点,把 <= 改成 < 即可
		while (top >= 2 && sgn(cross(hull[top - 2], hull[top - 1], P[i])) <= 0) {
			top--;
		}
		hull[top++] = P[i];
	}
	
	// 3. 求上凸壳
	int tmp = top; // 记录下凸壳的元素个数,上凸壳弹栈时不能破坏下凸壳
	for (int i = n - 2; i >= 0; i--) {
		while (top > tmp && sgn(cross(hull[top - 2], hull[top - 1], P[i])) <= 0) {
			top--;
		}
		hull[top++] = P[i];
	}
	
	if (n > 1) top--;
	hull.resize(top);
	return hull;
}
int hull_diam(vector<Point>& hull){
	int j=2;
	int ans=0,H=hull.size();
	if (H == 2) {
        return dist(hull[0], hull[1]) ;
    }
    if (H <= 1) {
        return 0;
    }
	up(i,0,H-1){
		int next_i=(i+1)%H;
		while(cross(hull[i],hull[next_i],hull[j])<=cross(hull[i],hull[next_i],hull[(j+1)%H])){
			j=(j+1)%H;
		}
		ans=max(ans,dist(hull[i],hull[j]));
		ans=max(ans,dist(hull[next_i],hull[j]));
	}
	return ans;   
}
void solve(){
	cin>>n;
	vector<Point>pts(n);
	up(i,0,n-1)cin>>pts[i].x>>pts[i].y;
	vector<Point>hull=convex_hull(pts);
	cout<<hull_diam(hull);
}

signed main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t = 1;
	// cin >> t;
	while (t--){
		solve();
	}
//	system("x-www-browser https://ys.mihoyo.com/");
//	cout << fixed << setprecision(10) << x << '\n';
	return 0;
}
/*
1
38133 49107

2 27269


*/
三点坐标解圆方程 (Circle Through Three Points) 大暴力
53 行
CPP JSON
【三点坐标解圆方程 (Circle Through Three Points)(大暴力)】 计算几何算法模板。 核心函数: void CL(无参数) — 核心算法函数 void calc(Poi a,Poi c) — 计算函数 void calc_(Poi a,Re K) — 计算函数 Poi Get_half(Poi a,Poi b) — 获取值 Poi Get_LPL(Line a,Line b) — 获取值 LD S(Re a) — 核心算法函数 LD Get_dis(Poi a,Poi b) — 获取值 核心结构体:Poi, Line 说明:freopen("123.txt","r",stdin);;printf("(x - %.3lf)^2 + (y - %.3lf)^2 = %.3lf^2\n",xin.x,xin.y,R);//��׼ʽ 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 52 行 CPP
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define Re register LD
#define abs(x) (x<0?-x:x)
#define sakura(x) (x<0?'-':'+')
using namespace std;
struct Poi{LD x,y;inline void CL(){x=y=0;}}a1,a2,a3,xin;
struct Line{
	LD k,b;
	inline void CL(){k=b=0;}
	inline void calc(Poi a,Poi c){k=(a.y-c.y)/(a.x-c.x),b=a.y-k*a.x;}// 由两点确定一条直线 
	inline void calc_(Poi a,Re K){k=K,b=a.y-k*a.x;}
}L1,L2,L3,L4;
inline Poi Get_half(Poi a,Poi b){// 求两圆交点 
	Poi c;
	c.x=(a.x+b.x)/2.0,c.y=(a.y+b.y)/2.0;
	return c;
}
inline Poi Get_LPL(Line a,Line b){
	Poi c;
	c.x=(b.b-a.b)/(a.k-b.k),c.y=a.k*c.x+a.b;
	return c;
}
inline LD S(Re a){return a*a;}
inline LD Get_dis(Poi a,Poi b){// 撤销操作� 
	return sqrt(S(a.x-b.x)+S(a.y-b.y));
}
LD R;
int main(){
//	freopen("123.txt","r",stdin); 
	while(scanf("%lf%lf%lf%lf%lf%lf",&a1.x,&a1.y,&a2.x,&a2.y,&a3.x,&a3.y)!=EOF){
		xin.CL(),L1.CL(),L2.CL(),L3.CL(),L4.CL();
		L1.calc(a1,a2),L2.calc(a2,a3);
		L3.calc_(Get_half(a1,a2),-1.0/L1.k);
		L4.calc_(Get_half(a2,a3),-1.0/L2.k);
		xin=Get_LPL(L3,L4);
		R=Get_dis(xin,a1);
		Re a=-xin.x,b=-xin.y,c=R,d=-2.0*xin.x,e=-2.0*xin.y,f=S(xin.x)+S(xin.y)-S(R);
		if(a!=0)printf("(x %c %.3lf)^2 ",sakura(a),abs(a));
        else printf("x^2 ");
        if(b!=0)printf("+ (y %c %.3lf)^2 ",sakura(b),abs(b));
        else printf("+ y^2 ");
        printf("= %.3lf^2\n",c);
        printf("x^2 + y^2");
        if(d!=0)printf(" %c %.3lf%c",sakura(d),abs(d),'x');
        if(e!=0)printf(" %c %.3lf%c",sakura(e),abs(e),'y');
        if(f!=0)printf(" %c %.3lf%c",sakura(f),abs(f),' ');
        printf("= 0\n\n");
	}
}
三点坐标解圆方程 (Circle Through Three Points) 解方程
40 行
CPP JSON
【三点坐标解圆方程 (Circle Through Three Points)(解方程)】 计算几何算法模板。 核心函数: Circle getcircle(Point A,Point B,Point C) — 获取值 void print(Point O,LD r) — 核心算法函数 核心结构体:Point, Circle 说明:printf("(%.3lf,%.3lf), D=%.3lf E=%.3lf F=%.3lf\n",D/2.0,E/2.0,D,E,F);;freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 39 行 CPP
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
#define S(a) ((a)*(a))
using namespace std;
struct Point{LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}};
struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};
inline Circle getcircle(Point A,Point B,Point C){
	LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
	LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
	LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
	LD F=-(S(x1)+S(y1)+D*x1+E*y1);
//	printf("(%.3lf,%.3lf), D=%.3lf E=%.3lf F=%.3lf\n",D/2.0,E/2.0,D,E,F);
	return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}
#define abs(x) (x<0?-x:x)
#define sakura(x) (x<0?'-':'+')
inline void print(Point O,LD r){
	LD a=-O.x,b=-O.y,c=r,d=-2.0*O.x,e=-2.0*O.y,f=S(O.x)+S(O.y)-S(r);
	if(a!=0)printf("(x %c %.3lf)^2 ",sakura(a),abs(a));
    else printf("x^2 ");
    if(b!=0)printf("+ (y %c %.3lf)^2 ",sakura(b),abs(b));
    else printf("+ y^2 ");
    printf("= %.3lf^2\n",c);
    printf("x^2 + y^2");
    if(d!=0)printf(" %c %.3lf%c",sakura(d),abs(d),'x');
    if(e!=0)printf(" %c %.3lf%c",sakura(e),abs(e),'y');
    if(f!=0)printf(" %c %.3lf%c",sakura(f),abs(f),' ');
    printf("= 0\n\n");
}
int main(){
//	freopen("123.txt","r",stdin);
	LD a,b,c,d,e,f;
	while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)!=EOF){
		Circle C=getcircle(Point(a,b),Point(c,d),Point(e,f));print(C.O,C.r);
	}
}
三角剖分 Hdu4404 多边形与圆的交
97 行
CPP JSON
【三角剖分(Hdu4404 多边形与圆的交)】 三角剖分(Triangulation)相关模板。 核心函数: int dcmp(LD a) — 核心算法函数 LD Abs(LD a) — 核心算法函数 void in(Re &x) — 核心算法函数 LD LDin(无参数) — 核心算法函数 void in(无参数) — 核心算法函数 LD Dot(Vector a,Vector b) — 点积运算 LD Cro(Vector a,Vector b) — 核心算法函数 LD Len(Vector a) — 核心算法函数 核心结构体:Point 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin);;printf("O=(%.2lf,%.2lf), R=%d\n",O.x,O.y,R); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 96 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=1e5+3;
const LD eps=1e-8,Pi=acos(-1.0);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
inline LD Abs(LD a){return a*dcmp(a);}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LD LDin(){
    LD X=0,Y=1.0;int f=0;char c=getchar();
    while(c<'0'||c>'9'){f|=c=='-';c=getchar();} 
    while(c>='0'&&c<='9')X=X*10+(c^48),c=getchar(); 
    if(c=='.'){c=getchar();while(c>='0'&&c<='9')X+=(Y/=10)*(c^48),c=getchar();}
    return f?-X:X;
}
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){x=LDin(),y=LDin();}
    inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}
};
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool operator==(Vector a,Vector b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}
inline Point turn_P(Point a,LD theta){
    LD x=a.x*cos(theta)+a.y*sin(theta);
    LD y=-a.x*sin(theta)+a.y*cos(theta);
    return Point(x,y);
}
inline Point cross_LL(Point a,Point b,Point c,Point d){
    Vector x=b-a,y=d-c,z=a-c;
    return a+x*(Cro(y,z)/Cro(x,y));
}
inline LD dis_PL(Point p,Point a,Point b){
    if(a==b)return Len(p-a);
    Vector x=p-a,y=p-b,z=b-a;
    if(dcmp(Dot(x,z))<0)return Len(x);
    if(dcmp(Dot(y,z))>0)return Len(y);
    return Abs(Cro(x,z)/Len(z));
}
inline Point FootPoint(Point p,Point a,Point b){
    Vector x=p-a,y=p-b,z=b-a;
    LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z);
    return a+z*(len1/(len1+len2));
}
inline LD calc(Point A,Point B,Point O,LD R){
    if((A==O)||(B==O))return 0;
    Re op=(dcmp(Cro(A-O,B-O))>0)?1:-1;LD ans=0;
    Vector x=A-O,y=B-O;
    Re flag1=(int)(dcmp(Len(x)-R)>0),flag2=(int)(dcmp(Len(y)-R)>0);
    if(!flag1&&!flag2)ans=Abs(Cro(A-O,B-O))/2.0;
    else if(flag1&&flag2){
        if(dcmp(dis_PL(O,A,B)-R)>=0)ans=R*R*Angle(x,y)/2.0;
        else{
            if(dcmp(Cro(A-O,B-O))>0)swap(A,B);
            Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
            Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point B_=F+z,A_=F-z;
            ans=R*R*(Angle(A-O,A_-O)+Angle(B-O,B_-O))/2.0+Cro(B_-O,A_-O)/2.0;
        }
    }
    else{
        if(flag1)swap(A,B);
        Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
        Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point C=(dcmp(Cro(A-O,B-O))>0)?(F-z):(F+z);
        ans=Abs(Cro(A-O,C-O))/2.0+R*R*Angle(C-O,B-O)/2.0;
    }
    return ans*op;
}
Point V,P[N];LD h,t,g,v0,ans,theta;int n;Point O;LD R;
int main(){
//    freopen("123.txt","r",stdin);
    while(~scanf("%lf",&O.x)){
        O.y=LDin(),v0=LDin(),theta=LDin(),t=LDin(),g=LDin(),R=LDin();
        if(!dcmp(O.x)&&!dcmp(O.y)&&!dcmp(v0)&&!dcmp(theta)&&!dcmp(t)&&!dcmp(g)&&!dcmp(R))break;
        theta=theta/180.0*Pi,O.x+=t*v0*cos(theta),O.y+=t*v0*sin(theta)-0.5*g*t*t,ans=0;
//        printf("O=(%.2lf,%.2lf), R=%d\n",O.x,O.y,R);
        in(n);for(Re i=1;i<=n;++i)P[i].in();
        for(Re i=1;i<=n;++i)ans+=calc(P[i],P[i<n?i+1:1],O,R);
        if(!dcmp(ans))puts("0.00");
        else printf("%.2lf\n",Abs(ans));
    }
}
三角形面积并 optimize
75 行
CPP JSON
【三角形面积并】 计算几何算法模板。 核心函数: int dcmp(Rd a) — 核心算法函数 void in(无参数) — 核心算法函数 void in(无参数) — 核心算法函数 bool cmp(Triangle A,Triangle B) — 核心算法函数 LD F(Rd Y) — 核心算法函数 LD Simpson(Rd L,Rd R) — 核心算法函数 LD sakura(Rd L,Rd R,Rd now) — 后缀数组 int TIT(Triangle A,Triangle B) — 核心算法函数 核心结构体:Point, Segment, Triangle 关键配置: N=2003 说明:freopen("456.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 74 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#define LD double
#define LL long long
#define Re register int
#define Rd register LD
#define Vector Point
using namespace std;
const int N=2003;
const LD eps=1e-9;
int n,m;map<LD,LD>vis;
inline int dcmp(Rd a){return a<-eps?-1:(a>eps?1:0);}
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
};
struct Segment{
    LD L,R;Segment(LD l=0,LD r=0){L=l,R=r;}
    inline bool operator<(Segment O)const{return L!=O.L?L<O.L:R<O.R;}
}Seg[N];
struct Triangle{
	LD x,y,m,L,R,D,U;
	inline void in(){scanf("%lf%lf%lf",&x,&y,&m),L=x,R=x+m,D=y,U=y+m;}
}C[N],C_[N];
inline bool cmp(Triangle A,Triangle B){return A.m<B.m;}
inline LD F(Rd Y){
    if(vis[Y])return vis[Y];
    Re t=0;Rd ans=0;
    for(Re i=1;i<=n;++i)
        if(dcmp(Y-C[i].D)>=0&&dcmp(Y-C[i].U)<0){
			Rd tmp=C[i].U-Y;
			if(dcmp(tmp)>0)Seg[++t]=Segment(C[i].x,C[i].x+tmp);
		}
    if(!t)return 0.0;
    sort(Seg+1,Seg+t+1);
    for(Re i=1,j;i<=t;i=j+1){
        Rd L=Seg[i].L,R=Seg[i].R;j=i;
        while(j<t&&Seg[j+1].L<=R)++j,R=max(R,Seg[j].R);
        ans+=R-L;
    }
    return vis[Y]=ans;
}
inline LD Simpson(Rd L,Rd R){return (R-L)*(F(L)+4.0*F((L+R)*0.5)+F(R))/6.0;}
inline LD sakura(Rd L,Rd R,Rd now){
    Rd mid=(L+R)*0.5,FL=Simpson(L,mid),FR=Simpson(mid,R);
    if(!dcmp(now-FL-FR))return now;
    return sakura(L,mid,FL)+sakura(mid,R,FR);
}
inline int TIT(Triangle A,Triangle B){
	return A.L>=B.L&&A.R<=B.R&&A.D>=B.D&&A.U<=B.U&&dcmp(A.R-(B.x+B.U-A.y))<=0;
}
LD ans,YY[N<<1];
int main(){
//	freopen("456.txt","r",stdin);
    scanf("%d",&m);Re t=0;
    for(Re i=1;i<=m;++i)C_[i].in();
    sort(C_+1,C_+m+1,cmp),C[++n]=C_[m];
    for(Re i=m-1;i>=1;--i){
        Re flag=1;
        for(Re j=1;j<=n&&flag;++j)if(TIT(C_[i],C[j]))flag=0;
        if(flag)C[++n]=C_[i];
    }
    for(Re i=1;i<=n;++i)YY[++t]=C[i].D,YY[++t]=C[i].U;
	sort(YY+1,YY+t+1);
    for(Re i=2;i<=t;++i)
		if(dcmp(YY[i]-YY[i-1])>0){
			Rd D=YY[i-1],U=YY[i]-2*eps;
	        ans+=sakura(D,U,Simpson(D,U));
    	}
    printf("%.1lf",ans);
}
二维凸包 周长
49 行
CPP JSON
【二维凸包(周长)】 计算几何算法模板。 核心函数: int dcmp(LD a) — 核心算法函数 LD Dot(Vector a,Vector b) — 点积运算 LD Cro(Vector a,Vector b) — 核心算法函数 LD Len(Vector a) — 核心算法函数 LD Angle(Vector a,Vector b) — 核心算法函数 Vector Normal(Vector a) — 核心算法函数 bool cmp1(Vector a,Vector b) — 核心算法函数 bool cmp2(Vector a,Vector b) — 核心算法函数 核心结构体:Point 关键配置: N=1e4+3 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 48 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define Vector Point
#define Re register int
using namespace std;
const int N=1e4+3;
const LD eps=1e-8;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
struct Point{LD x,y;Point(LD X=0,LD Y=0):x(X),y(Y){}}Poi[N],cp[N];
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}
inline Vector Normal(Vector a){LD L=Len(a);return Vector(-a.y/L,a.x/L);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline Vector operator/(Vector a,LD b){return Vector(a.x/b,a.y/b);}
inline bool cmp1(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;};
inline bool cmp2(Vector a,Vector b){
	LD pan=Cro(a-Poi[0],b-Poi[0]);
	return pan>0||(pan==0&&Len(a-Poi[0])<Len(b-Poi[0]));
};
inline int ConvexHull(Point *P,Re n,Point *cp){
	sort(P+1,P+n+1,cmp1);
	Re t=0;
	for(Re i=1;i<=n;++i){
		while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
		cp[++t]=P[i];
	}
	Re St=t;
	for(Re i=n-1;i>=1;--i){
		while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
		cp[++t]=P[i];
	}
	return --t;
}
int n;LD ans;
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%d",&n);
	for(Re i=1;i<=n;++i)scanf("%lf%lf",&Poi[i].x,&Poi[i].y);
	Re cnt=ConvexHull(Poi,n,cp);
	for(Re i=1;i<=cnt;++i)ans+=Len(cp[i<cnt?i+1:1]-cp[i]);
	printf("%.2lf\n",ans);
}
动态凸包 Professor's task
56 行
CPP JSON
【动态凸包(Professor's task)】 计算几何算法模板。 核心函数: void in(Re &x) — 核心算法函数 void In(无参数) — 核心算法函数 LL Cro(Vector a,Vector b) — 核心算法函数 int PIP(Point P) — 核心算法函数 int judge(IT it) — 判定函数 void insert(Point P) — 插入元素 核心结构体:Point, ConvexHull 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 55 行 CPP
#include<algorithm>
#include<cstdio>
#include<set>
#define LL long long
#define Vector Point
#define Re register int
#define IT set<Point>::iterator
using namespace std;
const int inf=2e9;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Point{
    LL x,y;Point(LL X=0,LL Y=0){x=X,y=Y;}
    inline void In(){Re X,Y;in(X),in(Y),x=X,y=Y;}
    inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}
}P;
inline LL Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
struct ConvexHull{
	int op;set<Point>s;
	inline int PIP(Point P){
		IT it=s.lower_bound(Point(P.x,-inf));
		if(it==s.end())return 0;
		if(it->x==P.x)return (P.y-it->y)*op<=0;
		if(it==s.begin())return 0;
		IT j=it,k=it;--j;return Cro(P-*j,*k-*j)*op>=0;
	}
	inline int judge(IT it){
		IT j=it,k=it;
		if(j==s.begin())return 0;--j;
		if(++k==s.end())return 0;
		return Cro(*it-*j,*k-*j)*op>=0;
	}
	inline void insert(Point P){
		if(PIP(P))return;
		IT tmp=s.lower_bound(Point(P.x,-inf));if(tmp!=s.end()&&tmp->x==P.x)s.erase(tmp);
		s.insert(P);IT it=s.find(P),p=it;
		if(p!=s.begin()){--p;while(judge(p)){IT tmp=p--;s.erase(tmp);}}
		if((p=++it)!=s.end())while(judge(p)){IT tmp=p++;s.erase(tmp);}
	}
}up,down;
int x,y,T,op;
int main(){
//	freopen("123.txt","r",stdin);
	in(T),up.op=1,down.op=-1;
	while(T--){
		in(op),P.In();
		if(op<2)up.insert(P),down.insert(P);
		else puts((up.PIP(P)&&down.PIP(P))?"YES":"NO");
	}
}
圆的面积并 optimize
75 行
CPP JSON
#pragma GCC optimize(3,"Ofast","inline")
C++ 74 行 CPP
//#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#define LD double
#define LL long long
#define Re register int
#define Rd register LD
#define Vector Point
using namespace std;
const int N=2003;
const LD eps=1e-13;
int n,m;map<LD,LD>vis;
inline int dcmp(Rd a){return a<-eps?-1:(a>eps?1:0);}
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
};
struct Segment{
    LD L,R;Segment(LD l=0,LD r=0){L=l,R=r;}
    inline bool operator<(Segment O)const{return L!=O.L?L<O.L:R<O.R;}
}Seg[N];
struct Circle{
    LD x,y,r,L,R,D,U;
    inline void in(){scanf("%lf%lf%lf",&x,&y,&r),L=x-r,R=x+r,D=y-r,U=y+r;}
    inline bool operator<(Circle B)const{return D<B.D;}
}C[N],C_[N];
inline bool cmp(Circle A,Circle B){return A.r<B.r;}
inline LD dis(Circle A,Circle B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
inline LD SS(Rd x){return x*x;}
inline LD F(Rd Y){
    if(vis[Y])return vis[Y];
    Re t=0;Rd ans=0;
    for(Re i=1;i<=n;++i)
        if(dcmp(Y-C[i].D)>0&&dcmp(Y-C[i].U)<0){
            Rd tmp=sqrt(SS(C[i].r)-SS(C[i].y-Y));
            if(dcmp(tmp)>0)Seg[++t]=Segment(C[i].x-tmp,C[i].x+tmp);
        }
    if(!t)return 0.0;
    sort(Seg+1,Seg+t+1);
    for(Re i=1,j;i<=t;i=j+1){
        Rd L=Seg[i].L,R=Seg[i].R;j=i;
        while(j<t&&Seg[j+1].L<=R)++j,R=max(R,Seg[j].R);
        ans+=R-L;
    }
    return vis[Y]=ans;
}
inline LD Simpson(Rd L,Rd R){return (R-L)*(F(L)+4.0*F((L+R)*0.5)+F(R))/6.0;}
inline LD sakura(Rd L,Rd R,Rd now){
    Rd mid=(L+R)*0.5,FL=Simpson(L,mid),FR=Simpson(mid,R);
    if(!dcmp(now-FL-FR))return now;
    return sakura(L,mid,FL)+sakura(mid,R,FR);
}
LD ans;
int main(){
//    freopen("789.txt","r",stdin);
    scanf("%d",&m);
    for(Re i=1;i<=m;++i)C_[i].in();
    sort(C_+1,C_+m+1,cmp),C[++n]=C_[m];
    for(Re i=m-1;i>=1;--i){
        Re flag=1;
        for(Re j=1;j<=n&&flag;++j)
			if(dcmp(C_[i].r-C[j].r+dis(C_[i],C[j]))<=0)flag=0;
        if(flag)C[++n]=C_[i];
    }
    sort(C+1,C+n+1);
    for(Re i=1,j;i<=n;i=j+1){
        Rd D=C[i].D,U=C[i].U;j=i;
        while(j<n&&C[j+1].D<=U)++j,U=max(U,C[j].U);
        ans+=sakura(D,U,Simpson(D,U));
    }
    printf("%.3lf",ans);
}
旋转卡壳 最远点对距离平方
49 行
CPP JSON
【旋转卡壳(最远点对距离平方)】 旋转卡壳(Rotating Calipers)模板,求凸包直径/最远点对。 核心函数: int dcmp(Rd a) — 核心算法函数 void in(无参数) — 核心算法函数 LD Dot(Vector a,Vector b) — 点积运算 LD Cro(Vector a,Vector b) — 核心算法函数 LD Len(Vector a) — 核心算法函数 bool cmp(Point a,Point b) — 核心算法函数 int ConvexHull(Point *P,Re n,Point *cp) — 核心算法函数 核心结构体:Point 关键配置: N=50003 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 48 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Rd register LD
#define Re register int
using namespace std;
const int N=50003;
const LD eps=1e-8;
inline int dcmp(Rd a){return a<-eps?-1:(a>eps?1:0);}
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
}cp[N],Poi[N];
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return Dot(a,a);}
inline Vector operator-(Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
inline bool cmp(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
inline int ConvexHull(Point *P,Re n,Point *cp){
	sort(P+1,P+n+1,cmp);
	Re t=0;
	for(Re i=1;i<=n;++i){
		while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
		cp[++t]=P[i];
	}
	Re St=t;
	for(Re i=n-1;i>=1;--i){
		while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
		cp[++t]=P[i];
	}
	return --t;
}
int n;
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%d",&n);
	for(Re i=1;i<=n;++i)Poi[i].in();
	Re cnt=ConvexHull(Poi,n,cp);
	Rd Ans=Len(cp[2]-cp[1]);
	for(Re i=1,j=3;i<=cnt;++i){
		while(dcmp(Cro(cp[i+1]-cp[i],cp[j]-cp[i])-Cro(cp[i+1]-cp[i],cp[j+1]-cp[i]))<0)j=j<cnt?j+1:1;
		Ans=max(Ans,max(Len(cp[j]-cp[i]),Len(cp[j]-cp[i+1])));
	}
	printf("%lld\n",(LL)(Ans+0.5));
}
最小圆覆盖 随机增量法
50 行
CPP JSON
【最小圆覆盖(随机增量法)】 计算几何算法模板。 核心函数: int dcmp(LD a) — 核心算法函数 void in(无参数) — 核心算法函数 LD Dot(Vector a,Vector b) — 点积运算 LD Len(Vector a) — 核心算法函数 Circle getcircle(Point A,Point B,Point C) — 获取值 int PIC(Circle &C,Point a) — 核心算法函数 void Random(无参数) — 核心算法函数 核心结构体:Point, Circle 关键配置: N=1e6+3 说明:freopen("123.txt","r",stdin);;random_shuffle(P+1,P+n+1); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 49 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
#define S(a) ((a)*(a))
using namespace std;
const int N=1e6+3;
const LD eps=1e-8;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}// 撤销操作
int n;
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
}P[N];
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};
inline Circle getcircle(Point A,Point B,Point C){
	LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
	LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
	LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
	LD F=-(S(x1)+S(y1)+D*x1+E*y1);
	return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}
inline int PIC(Circle &C,Point a){return dcmp(Len(a-C.O)-C.r)<=0;}
inline void Random(){for(Re i=1;i<=n;++i)swap(P[i],P[rand()%n+1]);}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%d",&n);
	for(Re i=1;i<=n;++i)P[i].in();
//	random_shuffle(P+1,P+n+1);
	Random();Circle C=Circle(P[1],0);
	for(Re i=2;i<=n;++i)
		if(!PIC(C,P[i])){
			C=Circle(P[i],0);
			for(Re j=1;j<i;++j)
				if(!PIC(C,P[j])){
					C.O=(P[i]+P[j])*0.5,C.r=Len(P[j]-C.O);
					for(Re k=1;k<j;++k)if(!PIC(C,P[k]))C=getcircle(P[i],P[j],P[k]);
				}
		}
	printf("%.2lf %.2lf %.2lf\n",C.O.x,C.O.y,C.r);
}
自适应辛普森积分 全局精度
24 行
CPP JSON
【自适应辛普森积分(全局精度)】 计算几何算法模板。 核心函数: int dcmp(LD a) — 核心算法函数 LD F(LD x) — 核心算法函数 LD Simpson(LD L,LD R) — 核心算法函数 LD sakura(LD L,LD R,LD now) — 后缀数组 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 23 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
#define Vector Point
using namespace std;
const LD eps=1e-13;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
LD a,b,c,d,L,R;
inline LD F(LD x){return (c*x+d)/(a*x+b);}
inline LD Simpson(LD L,LD R){return (R-L)*(F(L)+4.0*F((L+R)*0.5)+F(R))/6.0;}
inline LD sakura(LD L,LD R,LD now){
	LD mid=(L+R)*0.5,FL=Simpson(L,mid),FR=Simpson(mid,R);
	if(!dcmp(now-FL-FR))return now;
	return sakura(L,mid,FL)+sakura(mid,R,FR);
}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&L,&R);
	printf("%lf\n",sakura(L,R,Simpson(L,R)));
}
自适应辛普森积分 局部精度
24 行
CPP JSON
【自适应辛普森积分(局部精度)】 计算几何算法模板。 核心函数: int dcmp(LD a,LD eps) — 核心算法函数 LD F(LD x) — 核心算法函数 LD Simpson(LD L,LD R) — 核心算法函数 LD sakura(LD L,LD R,LD now,LD eps) — 后缀数组 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 23 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
#define Vector Point
using namespace std;
const LD eps=1e-7;
inline int dcmp(LD a,LD eps){return a<-eps?-1:(a>eps?1:0);}
LD a,b,c,d,L,R;
inline LD F(LD x){return (c*x+d)/(a*x+b);}
inline LD Simpson(LD L,LD R){return (R-L)*(F(L)+4.0*F((L+R)*0.5)+F(R))/6.0;}
inline LD sakura(LD L,LD R,LD now,LD eps){
	LD mid=(L+R)*0.5,FL=Simpson(L,mid),FR=Simpson(mid,R);
	if(!dcmp(now-FL-FR,eps))return now;
	return sakura(L,mid,FL,eps/2)+sakura(mid,R,FR,eps/2);
}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&L,&R);
	printf("%lf\n",sakura(L,R,Simpson(L,R),eps));
}
计算几何基础 全家桶
241 行
CPP JSON
【计算几何基础(全家桶)】 计算几何算法模板。 核心函数: int dcmp(LD a) — 核心算法函数 LD Abs(LD a) — 核心算法函数 void in(无参数) — 核心算法函数 void out(无参数) — 核心算法函数 LD Dot(Vector a,Vector b) — 点积运算 LD Cro(Vector a,Vector b) — 核心算法函数 LD Len(Vector a) — 核心算法函数 LD Angle(Vector a,Vector b) — 核心算法函数 核心结构体:Point, Line, Circle 关键配置: N=262144+3 说明:PA,AB������P��AB֮��(��ʵҲ������len(p-a)+len(p-b)==len(a-b)�жϣ����Ǿ�����ʧ�ϴ�);�㰴��ʱ�����;random_shuffle(P+1,P+n+1); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 240 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>


#define LD double
#define LL long long
#define Re register int
#define Vector Point
using namespace std;
const int N=262144+3;
const LD eps=1e-8,Pi=acos(-1.0);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}// 撤销操作
inline LD Abs(LD a){return a*dcmp(a);}
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
    inline void out(){printf("%.2lf %.2lf\n",x,y);}
};


inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}// 撤销操作�нǡ�
inline Vector Normal(Vector a){return Vector(-a.y,a.x);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool operator==(Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}



inline Point turn_P(Point a,LD theta){
    LD x=a.x*cos(theta)+a.y*sin(theta);
    LD y=-a.x*sin(theta)+a.y*cos(theta);
    return Point(x,y);
}
inline Point turn_PP(Point a,Point b,LD theta){
    LD x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x;
    LD y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y;
    return Point(x,y);
}



inline int pan_PL(Point p,Point a,Point b){
    return !dcmp(Cro(p-a,b-a))&&dcmp(Dot(p-a,p-b))<=0;
}
inline LD dis_PL(Point p,Point a,Point b){
    if(a==b)return Len(p-a);//AB�غ�
    Vector x=p-a,y=p-b,z=b-a;
    if(dcmp(Dot(x,z))<0)return Len(x);
    if(dcmp(Dot(y,z))>0)return Len(y);
    return Abs(Cro(x,z)/Len(z));
}

inline int pan_PL_(Point p,Point a,Point b){
    return !dcmp(Cro(p-a,b-a));
}
inline Point FootPoint(Point p,Point a,Point b){
    Vector x=p-a,y=p-b,z=b-a;
    LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z);
    return a+z*(len1/(len1+len2));
}
inline Point Symmetry_PL(Point p,Point a,Point b){
    return p+(FootPoint(p,a,b)-p)*2;
}

inline Point cross_LL(Point a,Point b,Point c,Point d){
    Vector x=b-a,y=d-c,z=a-c;
    return a+x*(Cro(y,z)/Cro(x,y));
}
inline int pan_cross_L_L(Point a,Point b,Point c,Point d){
    return pan_PL(cross_LL(a,b,c,d),c,d);
}
inline int pan_cross_LL(Point a,Point b,Point c,Point d){
    LD c1=Cro(b-a,c-a),c2=Cro(b-a,d-a);
    LD d1=Cro(d-c,a-c),d2=Cro(d-c,b-c);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;
}

inline int PIP(Point *P,Re n,Point a){
    Re cnt=0;LD tmp;
    for(Re i=1;i<=n;++i){
        Re j=i<n?i+1:1;
        if(pan_PL(a,P[i],P[j]))return 2;
        if(a.y>=min(P[i].y,P[j].y)&&a.y<max(P[i].y,P[j].y))
            tmp=P[i].x+(a.y-P[i].y)/(P[j].y-P[i].y)*(P[j].x-P[i].x),cnt+=dcmp(tmp-a.x)>0;
    }
    return cnt&1;
}
inline int judge(Point a,Point L,Point R){
    return dcmp(Cro(L-a,R-a))>0;
}
inline int PIP_(Point *P,Re n,Point a){
    if(judge(P[1],a,P[2])||judge(P[1],P[n],a))return 0;
    if(pan_PL(a,P[1],P[2])||pan_PL(a,P[1],P[n]))return 2;
    Re l=2,r=n-1;
    while(l<r){
        Re mid=l+r+1>>1;
        if(judge(P[1],P[mid],a))l=mid;
        else r=mid-1;
    }
    if(judge(P[l],a,P[l+1]))return 0;
    if(pan_PL(a,P[l],P[l+1]))return 2;
    return 1;
}


inline int judge_PP(Point *A,Re n,Point *B,Re m){
    for(Re i1=1;i1<=n;++i1){
        Re j1=i1<n?i1+1:1;
        for(Re i2=1;i2<=m;++i2){
            Re j2=i2<m?i2+1:1;
            if(pan_cross_LL(A[i1],A[j1],B[i2],B[j2]))return 0;
            if(PIP(B,m,A[i1])||PIP(A,n,B[i2]))return 0;// 撤销操作�
        }
    }
    return 1;
}



inline LD PolyArea(Point *P,Re n){
    LD S=0;
    for(Re i=1;i<=n;++i)S+=Cro(P[i],P[i<n?i+1:1]);
    return S/2.0;
}





inline bool cmp1(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;};
inline int ConvexHull(Point *P,Re n,Point *cp){
    sort(P+1,P+n+1,cmp1);
    Re t=0;
    for(Re i=1;i<=n;++i){
        while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
        cp[++t]=P[i];
    }
    Re St=t;
    for(Re i=n-1;i>=1;--i){
        while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
        cp[++t]=P[i];
    }
    return --t;
}

struct Line{
    Point a,b;LD k;Line(Point A=Point(0,0),Point B=Point(0,0)){a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
    inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,a);}
}L[N],Q[N];
inline Point cross(Line L1,Line L2){return cross_LL(L1.a,L1.b,L2.a,L2.b);}
inline int judge(Line L,Point a){return dcmp(Cro(a-L.a,L.b-L.a))>0;}
inline int halfcut(Line *L,Re n,Point *P){
    sort(L+1,L+n+1);Re m=n;n=0;
    for(Re i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++n]=L[i];
    Re h=1,t=0;
    for(Re i=1;i<=n;++i){
        while(h<t&&judge(L[i],cross(Q[t],Q[t-1])))--t;
        while(h<t&&judge(L[i],cross(Q[h],Q[h+1])))++h;
        Q[++t]=L[i];
    }
    while(h<t&&judge(Q[h],cross(Q[t],Q[t-1])))--t;
    while(h<t&&judge(Q[t],cross(Q[h],Q[h+1])))++h;
    n=0;
    for(Re i=h;i<=t;++i)P[++n]=cross(Q[i],Q[i<t?i+1:h]);
    return n;
}

Vector V1[N],V2[N];
inline int Mincowski(Point *P1,Re n,Point *P2,Re m,Vector *V){
    for(Re i=1;i<=n;++i)V1[i]=P1[i<n?i+1:1]-P1[i];
    for(Re i=1;i<=m;++i)V2[i]=P2[i<m?i+1:1]-P2[i];
    Re t=0,i=1,j=1;V[++t]=P1[1]+P2[1];
    while(i<=n&&j<=m)++t,V[t]=V[t-1]+(dcmp(Cro(V1[i],V2[j]))>0?V1[i++]:V2[j++]);
    while(i<=n)++t,V[t]=V[t-1]+V1[i++];
    while(j<=m)++t,V[t]=V[t-1]+V2[j++];
    return t;
}



#define S(a) ((a)*(a))
struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};
inline Circle getCircle(Point A,Point B,Point C){
    LD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;
    LD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
    LD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);
    LD F=-(S(x1)+S(y1)+D*x1+E*y1);
    return Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));
}
inline Circle getcircle(Point A,Point B,Point C){
    Point P1=(A+B)*0.5,P2=(A+C)*0.5;
    Point O=cross_LL(P1,P1+Normal(B-A),P2,P2+Normal(C-A));
    return Circle(O,Len(A-O));
}

inline int PIC(Circle C,Point a){return dcmp(Len(a-C.O)-C.r)<=0;}
inline void Random(Point *P,Re n){for(Re i=1;i<=n;++i)swap(P[i],P[rand()%n+1]);}
inline Circle Min_Circle(Point *P,Re n){
//  random_shuffle(P+1,P+n+1);
    Random(P,n);Circle C=Circle(P[1],0);
    for(Re i=2;i<=n;++i)if(!PIC(C,P[i])){
        C=Circle(P[i],0);
        for(Re j=1;j<i;++j)if(!PIC(C,P[j])){
            C.O=(P[i]+P[j])*0.5,C.r=Len(P[j]-C.O);
            for(Re k=1;k<j;++k)if(!PIC(C,P[k]))C=getcircle(P[i],P[j],P[k]);
        }
    }
    return C;
}

inline LD calc(Point A,Point B,Point O,LD R){
    if(A==O||B==O)return 0;
    Re op=dcmp(Cro(A-O,B-O))>0?1:-1;LD ans=0;
    Vector x=A-O,y=B-O;
    Re flag1=dcmp(Len(x)-R)>0,flag2=dcmp(Len(y)-R)>0;
    if(!flag1&&!flag2)ans=Abs(Cro(A-O,B-O))/2.0;
    else if(flag1&&flag2){
        if(dcmp(dis_PL(O,A,B)-R)>=0)ans=R*R*Angle(x,y)/2.0;
        else{
            if(dcmp(Cro(A-O,B-O))>0)swap(A,B);
            Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
            Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point B_=F+z,A_=F-z;
            ans=R*R*(Angle(A-O,A_-O)+Angle(B-O,B_-O))/2.0+Cro(B_-O,A_-O)/2.0;
        }
    }
    else{
        if(flag1)swap(A,B);
        Point F=FootPoint(O,A,B);LD lenx=Len(F-O),len=sqrt(R*R-lenx*lenx);
        Vector z=turn_P(F-O,Pi/2.0)*(len/lenx);Point C=dcmp(Cro(A-O,B-O))>0?F-z:F+z;
        ans=Abs(Cro(A-O,C-O))/2.0+R*R*Angle(C-O,B-O)/2.0;
    }
    return ans*op;
}

int main(){}
闵可夫斯基和 战争
84 行
CPP JSON
【闵可夫斯基和(战争)】 计算几何算法模板。 核心函数: int dcmp(LD a) — 核心算法函数 void in(Re &x) — 核心算法函数 void in(无参数) — 核心算法函数 void print(Re op=0) — 核心算法函数 LD Dot(Vector a,Vector b) — 点积运算 LD Cro(Vector a,Vector b) — 核心算法函数 LD Len(Vector a) — 核心算法函数 bool cmp1(Vector a,Vector b) — 核心算法函数 核心结构体:Point 关键配置: N=1e5+3,inf=1e8 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 83 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=1e5+3,inf=1e8;
const LD eps=1e-8;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Point{
	LD x,y;LD k;Point(LD X=0,LD Y=0){x=X,y=Y;}
	inline void in(){scanf("%lf%lf",&x,&y);}
	inline void print(Re op=0){printf("(%.2lf %.2lf) ",x,y);if(op)puts("");}
};
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt(Dot(a,a));}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool cmp1(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;};
inline int ConvexHull(Point *P,Re n,Point *cp){
    sort(P+1,P+n+1,cmp1);
    Re t=0;
    for(Re i=1;i<=n;++i){
        while(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
        cp[++t]=P[i];
    }
    Re St=t;
    for(Re i=n-1;i>=1;--i){
        while(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;
        cp[++t]=P[i];
    }
    return --t;
}
inline int judge(Point a,Point L,Point R){
	return dcmp(Cro(L-a,R-a))>0;
}
inline int PIL(Point a,Point b,Point p){
	return !dcmp(Cro(p-a,b-a))&&dcmp(Cro(p-a,p-b))<0;
}
inline int PIP(Point *P,Re n,Point a){
	if(judge(P[1],a,P[2])||judge(P[1],P[n],a))return 0;
	if(PIL(P[1],P[2],a)||PIL(P[1],P[n],a))return 1;
	Re l=2,r=n-1;
	while(l<r){
		Re mid=l+r+1>>1;
		if(judge(P[1],P[mid],a))l=mid;
		else r=mid-1;
	}
	if(judge(P[l],a,P[l+1]))return 0;
	if(PIL(P[l],P[l+1],a))return 1;
	return 1;
}
Vector V1[N],V2[N];
inline int Mincowski(Point *P1,Re n,Point *P2,Re m,Vector *V){
	for(Re i=1;i<=n;++i)V1[i]=P1[i<n?i+1:1]-P1[i];
	for(Re i=1;i<=m;++i)V2[i]=P2[i<m?i+1:1]-P2[i];
	Re t=0,i=1,j=1;V[++t]=P1[1]+P2[1];
	while(i<=n&&j<=m)++t,V[t]=V[t-1]+(dcmp(Cro(V1[i],V2[j]))>0?V1[i++]:V2[j++]);
	while(i<=n)++t,V[t]=V[t-1]+V1[i++];
	while(j<=m)++t,V[t]=V[t-1]+V2[j++];
	return t;
}
int n,m,T;Point v,P1[N],P2[N],cp1[N],cp2[N];Vector V[N<<1];
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(T);
	for(Re i=1;i<=n;++i)P1[i].in();
	for(Re i=1;i<=m;++i)P2[i].in(),P2[i].x=-P2[i].x,P2[i].y=-P2[i].y;
	Re cnt1=ConvexHull(P1,n,cp1),cnt2=ConvexHull(P2,m,cp2);
	Re cnt=Mincowski(cp1,cnt1,cp2,cnt2,V); 
	while(T--)v.in(),printf("%d\n",PIP(V,cnt,v));
}
小凸爱跑步 直线不等式转半平面交
88 行
CPP JSON
【小凸爱跑步(直线不等式转半平面交)】 计算几何算法模板。 核心函数: int dcmp(LD a) — 核心算法函数 void in(Re &x) — 核心算法函数 void in(无参数) — 核心算法函数 LD Dot(Vector a,Vector b) — 点积运算 LD Cro(Vector a,Vector b) — 核心算法函数 int judge(Point a,Point L,Point R) — 判定函数 Point cross(Point a,Point b,Point c,Point d) — 叉积运算 LD PolyArea(Point *P,Re n) — 核心算法函数 核心结构体:Point, Line 关键配置: N=1e5+3,inf=2e9 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 87 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
const LD eps=1e-8;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
};
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline int judge(Point a,Point L,Point R){
    return dcmp(Cro(L-a,R-a))>0;
}
inline Point cross(Point a,Point b,Point c,Point d){
    Vector x=b-a,y=d-c,z=a-c;
    return a+x*(Cro(y,z)/Cro(x,y));
}
inline LD PolyArea(Point *P,Re n){
    LD ans=0;
    for(Re i=1;i<=n;++i)ans+=Cro(P[i],P[i<n?i+1:1]);
    return ans/2.0;
}
struct Line{
    Point a,b;LD k;Line(Point A=Point(0,0),Point B=Point(0,0)){a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
    inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,b);}
}Q[N<<1];
inline int judge(Point a,Line L){return dcmp(Cro(a-L.a,L.b-L.a))>0;}
inline Point cross(Line L1,Line L2){return cross(L1.a,L1.b,L2.a,L2.b);}
inline int halfcut(Line *L,Re n,Point *P){
    sort(L+1,L+n+1);Re m=0;
    for(Re i=1;i<=n;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++m]=L[i];
    Re h=1,t=0;
    for(Re i=1;i<=m;++i){
        while(h<t&&judge(cross(Q[t],Q[t-1]),L[i]))--t;
        while(h<t&&judge(cross(Q[h],Q[h+1]),L[i]))++h;
        Q[++t]=L[i];
    }
    while(h<t&&judge(cross(Q[t],Q[t-1]),Q[h]))--t;
    while(h<t&&judge(cross(Q[h],Q[h+1]),Q[t]))++h;
    m=0;
    for(Re i=h;i<=t;++i)P[++m]=cross(Q[i],Q[i<t?i+1:h]);
    return m;
}
int n,m;Point P[N],PP[N<<1];Line L[N<<1];
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)P[i].in();P[n+1]=P[1];
    for(Re i=2;i<=n;++i){
        Point tmp=P[1]-P[2]-P[i]+P[i+1];
        LD a=tmp.y,b=-tmp.x,c=Cro(P[1],P[2])-Cro(P[i],P[i+1]);//ax+by+c<=0
        if(!dcmp(a)&&!dcmp(b)){
            if(dcmp(c)<=0)continue;
            else{puts("0");return 0;}
        }
        if(!dcmp(a)){//by+c<=0
            if(b>0)L[++m]=Line(Point(1,-c/b),Point(0,-c/b));//y<=-c/b
            else L[++m]=Line(Point(0,-c/b),Point(1,-c/b));//y>=-c/b
        }
        else if(!dcmp(b)){//ax+c<=0
            if(a>0)L[++m]=Line(Point(-c/a,0),Point(-c/a,1));//x<=-c/a
            else L[++m]=Line(Point(-c/a,1),Point(-c/a,0));//x>=-c/a
        }
        else if(b>0)L[++m]=Line(Point(1,-a/b-c/b),Point(0,-c/b));//y<=-a/b*x-c/b
        else L[++m]=Line(Point(0,-c/b),Point(1,-a/b-c/b));//y>=-a/b*x-c/b
    }
    for(Re i=1;i<=n;++i)L[++m]=Line(P[i],P[i+1]);
    Re cnt=halfcut(L,m,PP);
    printf("%.4lf\n",PolyArea(PP,cnt)/PolyArea(P,n));
}
逃考 半平面交求点管辖区域
107 行
CPP JSON
【逃考(半平面交求点管辖区域)】 计算几何算法模板。 核心函数: int dcmp(LD a) — 核心算法函数 void in(无参数) — 核心算法函数 void print(无参数) — 核心算法函数 LD Dot(Vector a,Vector b) — 点积运算 LD Cro(Vector a,Vector b) — 核心算法函数 LD Len(Vector a) — 核心算法函数 Point cross(Point a,Point b,Point c,Point d) — 叉积运算 int judge(Point a,Point L,Point R) — 判定函数 核心结构体:Point, Line, Dijkstra, QAQ, QWQ 关键配置: N=610 说明:freopen("456.txt","r",stdin);;printf("st=%d\n",st); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 106 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=610;
const LD eps=1e-8,Pi=acos(-1);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
struct Point{
	LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
	inline void in(){scanf("%lf%lf",&x,&y);}
	inline void print(){printf("%.2lf %.2lf\n",x,y);}
}P[N];
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return Dot(a,a);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD x){return Vector(a.x*x,a.y*x);}
inline Point cross(Point a,Point b,Point c,Point d){
	Vector x=b-a,y=d-c,z=a-c;
	return a+x*(Cro(y,z)/Cro(x,y));
}
inline int judge(Point a,Point L,Point R){
	return dcmp(Cro(L-a,R-a))>0;
}
struct Line{
	Point a,b;LD k;int id;Line(Point A=Point(0,0),Point B=Point(0,0)){id=0,a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}
	inline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,b);}
}Q[N];
inline Point cross(Line L1,Line L2){return cross(L1.a,L1.b,L2.a,L2.b);}
inline int judge(Line L,Point a){return dcmp(Cro(a-L.a,L.b-L.a))>0;}
inline void halfcut(Line *L,Re &n){
	sort(L+1,L+n+1);Re m=n;n=0;
	for(Re i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++n]=L[i];
	Re h=1,t=0;
	for(Re i=1;i<=n;++i){
		while(h<t&&judge(L[i],cross(Q[t],Q[t-1])))--t;
		while(h<t&&judge(L[i],cross(Q[h],Q[h+1])))++h;
		Q[++t]=L[i];
	}
	while(h<t&&judge(Q[h],cross(Q[t],Q[t-1])))--t;
	while(h<t&&judge(Q[t],cross(Q[h],Q[h+1])))++h;
	n=0;
	for(Re i=h;i<=t;++i)L[++n]=Q[i];
}
inline Point turnP(Point a,LD theta){
	LD x=a.x*cos(theta)+a.y*sin(theta);
	LD y=a.y*cos(theta)-a.x*sin(theta);
	return Point(x,y);
}
inline Line get_midL(Point a,Point b){
	Point M=a+((b-a)*0.5);
	return Line(M,M+turnP(a-b,Pi/2.0));
}
int n,m,T,st,ed;Point a,b,c,d,x0,A[N];Line L[N];
struct Dijkstra{
	int o,dis[N],pan[N],head[N];
	struct QAQ{int w,to,next;}a[N*N];
	inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
	struct QWQ{int x,d;inline bool operator<(const QWQ &O)const{return d>O.d;}};
	priority_queue<QWQ>Q;
	inline void CL(){memset(head,0,sizeof(head)),o=0;}
	inline int dijkstra(Re st,Re ed){
		for(Re i=0;i<=n;++i)dis[i]=2e9,pan[i]=0;
		Q.push((QWQ){st,dis[st]=1});
		while(!Q.empty()){
			Re x=Q.top().x;Q.pop();
			if(pan[x])continue;
			pan[x]=1;
			for(Re i=head[x],to;i;i=a[i].next)
				if(dis[to=a[i].to]>dis[x]+a[i].w)
					Q.push((QWQ){to,dis[to]=dis[x]+a[i].w});
		}
		return dis[ed];
	}
}T1;
int main(){
//	freopen("456.txt","r",stdin);
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n),c.in(),x0.in(),T1.CL();
		if(!n){puts("0");continue;}
		a=Point(0,0),b=Point(c.x,0),d=Point(0,c.y);
		for(Re i=1;i<=n;++i){
			A[i].in();
			if(A[i].x>c.x||A[i].y>c.y){--i,--n;continue;}
			if(dcmp(Len(A[i]-x0)-Len(A[st]-x0))<0)st=i;
		}
//		printf("st=%d\n",st);
		for(Re i=1;i<=n;++i){
			Re m=0;
			for(Re j=1;j<=n;++j)
				if(i!=j)L[++m]=get_midL(A[i],A[j]),L[m].id=j;
			L[++m]=Line(a,b),L[++m]=Line(b,c),L[++m]=Line(c,d),L[++m]=Line(d,a);
			halfcut(L,m);
			for(Re j=1;j<=m;++j)T1.add(i,L[j].id,L[j].id>0);
		}
		printf("%d\n",T1.dijkstra(st,ed));
	}
}
防线修建 动态凸包 维护周长
143 行
CPP JSON
【防线修建(动态凸包 维护周长)】 计算几何算法模板。 核心函数: int dcmp(LD a) — 核心算法函数 LD Abs(LD a) — 核心算法函数 void in(Re &x) — 核心算法函数 void In(无参数) — 核心算法函数 LL Dot(Vector a,Vector b) — 点积运算 LL Cro(Vector a,Vector b) — 核心算法函数 LD Len(Vector a) — 核心算法函数 int which(Re p) — 核心算法函数 核心结构体:Point, Splay, QAQ, ConvexHull 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 142 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cmath>
#include<set>
#define LD double
#define LL long long
#define Vector Point
#define Re register int
using namespace std;
const int N=1e5+3;
const LD eps=1e-8,Pi=acos(-1.0);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
inline LD Abs(LD a){return a*dcmp(a);}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Point{
    LL x,y;Point(LL X=0,LL Y=0){x=X,y=Y;}
    inline void In(){Re X,Y;in(X),in(Y),x=X,y=Y;}
    inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}
};
inline LL Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
inline LL Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline LD Len(Vector a){return sqrt((LD)Dot(a,a));}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool operator==(Vector a,Vector b){return a.x==b.x&&a.y==b.y;}
struct Splay{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	#define pv tr[p].v
	int O,root;queue<int>Q;LD ans;
	struct QAQ{int fa,ps[2];Point v;}tr[N];
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		connect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);
	}
	inline void splay(Re p){
		for(Re fa;pf;rotate(p))
			if(tr[fa=pf].fa)rotate(which(p)==which(fa)?fa:p);
		root=p;
	}
	inline void CL(Re p){tr[p].v=Point(),pf=pl=pr=0,p=0;}
	inline int New(){
		Re p;
		if(Q.empty())p=++O;
		else p=Q.front(),Q.pop();
		return p;
	}
	inline void del(Re p){CL(p),Q.push(p);}
	inline int pre(Re p){p=pl;while(pr)p=pr;return p;}
	inline int nex(Re p){p=pr;while(pl)p=pl;return p;}
	inline void insert(Point v){
		Re p=root,fa=0;
		while(p)fa=p,p=tr[p].ps[!(pv<v)];
		p=New(),pv=v,pf=fa;
		if(fa)tr[fa].ps[!(tr[fa].v<v)]=p;
		splay(p);Re p1=0,p2=0;
		if(pl)p1=pre(p);if(pr)p2=nex(p);
		if(p1&&p2)ans-=Len(tr[p2].v-tr[p1].v);
		if(p1)ans+=Len(v-tr[p1].v);
		if(p2)ans+=Len(v-tr[p2].v);
	}
	inline void erase(Point v){
		Re p=root;
		while(!(pv==v))p,p=tr[p].ps[!(pv<v)];
		splay(p);
		Re p1=0,p2=0;
		if(pl)p1=pre(p);if(pr)p2=nex(p);
		if(p1&&p2)ans+=Len(tr[p2].v-tr[p1].v);
		if(p1)ans-=Len(v-tr[p1].v);
		if(p2)ans-=Len(v-tr[p2].v);
		if(!pl&&!pr){root=0,del(p);return;}
		if(!pl||!pr){tr[root=pl+pr].fa=0,del(p);return;}
		splay(pre(p)),tr[root].ps[1]=pr,tr[pr].fa=root,del(p);
	}
};
#define IT set<Point>::iterator
struct ConvexHull{
	int op;set<Point>s;LD ans;//Splay ss;
	inline void Insert(Point P){
		s.insert(P);IT p=s.find(P);
		Re o1=0,o2=0;IT p1=p,p2=p;
		if(p1!=s.begin())o1=1,--p1;if(++p2!=s.end())o2=1;
		if(o1&&o2)ans-=Len(*p2-*p1);
		if(o1)ans+=Len(*p-*p1);
		if(o2)ans+=Len(*p-*p2);
	}
	inline void Erase(IT p){
		Re o1=0,o2=0;IT p1=p,p2=p;
		if(p1!=s.begin())o1=1,--p1;if(++p2!=s.end())o2=1;
		if(o1&&o2)ans+=Len(*p2-*p1);
		if(o1)ans-=Len(*p-*p1);
		if(o2)ans-=Len(*p-*p2);
		s.erase(p);
	}
	inline int PIP(Point P){
		IT it=s.lower_bound(Point(P.x,-2e9));
		if(it==s.end())return 0;
		if(it->x==P.x)return (P.y-it->y)*op<=0;
		if(it==s.begin())return 0;
		IT j=it,k=it;--j;return Cro(P-*j,*k-*j)*op>=0;
	}
	inline int judge(IT it){
		IT j=it,k=it;
		if(j==s.begin())return 0;--j;
		if(++k==s.end())return 0;
		return Cro(*it-*j,*k-*j)*op>=0;
	}
	inline void insert(Point P){
		if(PIP(P))return;
		IT tmp=s.lower_bound(Point(P.x,-2e9));if(tmp!=s.end()&&tmp->x==P.x)Erase(tmp);//ss.erase(*tmp),s.erase(tmp);
		Insert(P);/*s.insert(P),ss.insert(P);*/IT it=s.find(P),p=it;
		if(p!=s.begin()){--p;while(judge(p)){IT tmp=p--;Erase(tmp);/*ss.erase(*tmp),s.erase(tmp);*/}}
		if((p=++it)!=s.end())while(judge(p)){IT tmp=p++;Erase(tmp);/*ss.erase(*tmp),s.erase(tmp);*/}
	}
}up,down;
int n,x,T,X[N],op[N],vis[N];LD Ans[N];Point P[N];
int main(){
//	freopen("123.txt","r",stdin);
	in(x),P[0].In(),up.op=1,down.op=-1;
	up.insert(P[0]),down.insert(P[0]);
	up.insert(Point(0,0)),down.insert(Point(0,0));
	up.insert(Point(x,0)),down.insert(Point(x,0));
	in(n);for(Re i=1;i<=n;++i)P[i].In();
	in(T);for(Re i=1;i<=T;++i){in(op[i]);if(op[i]<2)in(x),vis[X[i]=x]=1;}
	for(Re i=1;i<=n;++i)if(!vis[i])up.insert(P[i]),down.insert(P[i]);
	for(Re i=T;i>=1;--i)
		if(op[i]<2)up.insert(P[X[i]]),down.insert(P[X[i]]);
		else Ans[i]=up.ans+Len(*up.s.begin()-*down.s.begin())+Len(*--up.s.end()-*--down.s.end());
	for(Re i=1;i<=T;++i)if(op[i]>1)printf("%.2lf\n",Ans[i]);
}
扫描线(暴力) 周长
36 行
CPP JSON
【扫描线(暴力)(周长)】 扫描线(Sweep Line)模板,处理几何对象间的交并关系。 核心函数: void in(Re &x) — 核心算法函数 核心结构体:Line 关键配置: N=1e4 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 35 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define y1 ORZ_HYJ_AK_IOI
#define LL long long
#define Re register int
using namespace std;
const int N=1e4;
int a,b,c,d,n,m,pan1[N+5<<1],pan2[N+5<<1];LL ans;
struct Line{int x,y1,y2,k;inline bool operator<(Line O)const{return x==O.x?k>O.k:x<O.x;}}A[N+5<<1],B[N+5<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
    // freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i){
        in(a),in(b),in(c),in(d);
        A[++m]=(Line){a,b,d,1},B[m]=(Line){b,a,c,1};
        A[++m]=(Line){c,b,d,0},B[m]=(Line){d,a,c,0};
    }
    sort(A+1,A+m+1);
    sort(B+1,B+m+1);
    for(Re i=1;i<=m;++i){
        if(A[i].k)for(Re j=A[i].y1;j<A[i].y2;++j)ans+=(!pan1[j+N]),++pan1[j+N];
        else for(Re j=A[i].y1;j<A[i].y2;++j)--pan1[j+N],ans+=(!pan1[j+N]);
        if(B[i].k)for(Re j=B[i].y1;j<B[i].y2;++j)ans+=(!pan2[j+N]),++pan2[j+N];
        else for(Re j=B[i].y1;j<B[i].y2;++j)--pan2[j+N],ans+=(!pan2[j+N]);
    }
    printf("%lld\n",ans);
}
扫描线(线段树) 周长
58 行
CPP JSON
【扫描线(线段树)(周长)】 扫描线(Sweep Line)模板,处理几何对象间的交并关系。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p,Re L,Re R) — 上推更新节点信息 void change(Re p,Re L,Re R,Re l,Re r,Re v) — 核心算法函数 核心结构体:Segment_Tree, QAQ, Line 关键配置: N=5e4+3,M=2e4+3 说明:freopen("123.txt","r",stdin); 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3,M=2e4+3;
int n,m,ans,Max=10000,x1[N],y1[N],x2[N],y2[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	struct QAQ{int S,cnt;}tr[M<<2];
	inline void pushup(Re p,Re L,Re R){
		if(tr[p].cnt)tr[p].S=R-L+1;
		else tr[p].S=(L==R)?0:tr[pl].S+tr[pr].S;
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
		if(l<=L&&R<=r){tr[p].cnt+=v,pushup(p,L,R);return;}
		if(l<=mid)change(pl,L,mid,l,r,v);
		if(r>mid)change(pr,mid+1,R,l,r,v);
		pushup(p,L,R);
	}
}TR1,TR2;
struct Line{
	int x,y1,y2,k;Line(Re X=0,Re Y1=0,Re Y2=0,Re K=0){x=X,y1=Y1,y2=Y2,k=K;}
	inline bool operator<(const Line &O)const{return x!=O.x?x<O.x:k>O.k;}
}L1[N<<1],L2[N<<1];
int main(){
//	freopen("123.txt","r",stdin);
	in(n);
	for(Re i=1;i<=n;++i)
		in(x1[i]),in(y1[i]),in(x2[i]),in(y2[i]),x1[i]+=Max,y1[i]+=Max,x2[i]+=Max,y2[i]+=Max,
		L1[++m]=Line(x1[i],y1[i],y2[i],1),L2[m]=Line(y1[i],x1[i],x2[i],1),
		L1[++m]=Line(x2[i],y1[i],y2[i],-1),L2[m]=Line(y2[i],x1[i],x2[i],-1);
	sort(L1+1,L1+m+1),sort(L2+1,L2+m+1);
	for(Re i=1,j=0;i<=m;i=j+1){
		Re last=TR1.tr[1].S;
		++j,TR1.change(1,1,Max<<1,L1[j].y1+1,L1[j].y2,L1[j].k);
		while(j+1<=m&&L1[j].x==L1[j+1].x&&L1[j].k==L1[j+1].k)++j,TR1.change(1,1,Max<<1,L1[j].y1+1,L1[j].y2,L1[j].k);
		ans+=abs(last-TR1.tr[1].S);
	}
	for(Re i=1,j=0;i<=m;i=j+1){
		Re last=TR2.tr[1].S;
		++j,TR2.change(1,1,Max<<1,L2[j].y1+1,L2[j].y2,L2[j].k);
		while(j+1<=m&&L2[j].x==L2[j+1].x&&L2[j].k==L2[j+1].k)++j,TR2.change(1,1,Max<<1,L2[j].y1+1,L2[j].y2,L2[j].k);
		ans+=abs(last-TR2.tr[1].S);
	}
	printf("%d\n",ans);
}
扫描线 面积
48 行
CPP JSON
【扫描线(面积)】 扫描线(Sweep Line)模板,处理几何对象间的交并关系。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p,Re L,Re R) — 上推更新节点信息 void change(Re p,Re L,Re R,Re l,Re r,Re v) — 核心算法函数 核心结构体:Line, Segment_Tree, QAQ 关键配置: N=1e5+3 适用场景:几何对象的交并关系判定、面积/周长计算
C++ 47 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,T,x1,y1,x2,y2,b[N<<1];LL ans;
struct Line{int x,y1,y2,k;inline bool operator<(const Line &O)const{return x<O.x;}}A[N<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
    #define pl (p<<1)
    #define pr (p<<1|1)
    #define mid ((L+R)>>1)
    struct QAQ{int cnt,len;}tr[N<<3];
    inline void pushup(Re p,Re L,Re R){
        if(tr[p].cnt)tr[p].len=b[R+1]-b[L];
        else tr[p].len=(L==R)?0:tr[pl].len+tr[pr].len;
    }
    inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
        if(l<=L&&R<=r){tr[p].cnt+=v,pushup(p,L,R);return;}
        if(l<=mid)change(pl,L,mid,l,r,v);
        if(r>mid)change(pr,mid+1,R,l,r,v);
        pushup(p,L,R);
    }
}TR;
int main(){
    in(T);
    while(T--){
        in(x1),in(y1),in(x2),in(y2);
        A[++n]=(Line){x1,y1,y2,1},A[++n]=(Line){x2,y1,y2,-1};
        b[++m]=y1,b[++m]=y2;
    }
    sort(A+1,A+n+1),sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
    for(Re i=1;i<n;++i){
        Re y1=lower_bound(b+1,b+m+1,A[i].y1)-b,y2=lower_bound(b+1,b+m+1,A[i].y2)-b;
        TR.change(1,1,m-1,y1,y2-1,A[i].k);
        ans+=(LL)TR.tr[1].len*(A[i+1].x-A[i].x);
    }
    printf("%lld\n",ans);
}
已复制