两个代码只改了一行，一个T第一个点一个飞快AC。只改了个判断条件，而且（我认为）这个判断都是O(1)的。

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-4;
const double inf = 1e18;
const double pi = acos(-1.0);
const int maxp = 20005;

int sgn(double x)//判断正负
{
	if (fabs(x) < eps)return 0;
	if (x < 0)return -1;
	else return 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);
	}
	bool operator == (Point b)const
	{
		return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
	}
	bool operator < (Point b)const
	{
		return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
	}
	Point operator -(const Point& b)const
	{
		return Point(x - b.x, y - b.y);
	}
	double operator ^(const Point& b)const//叉积
	{
		return x * b.y - y * b.x;
	}
	double operator *(const Point& b)const//点积
	{
		return x * b.x + y * b.y;
	}
	double distance(Point p)//返回两点距离 求凸包时Point类只需该函数及以上的函数！
	{
		return hypot(x - p.x, y - p.y);
	}
	double len()//返回长度
	{
		return hypot(x, y);
	}
	Point operator +(const Point& b)const
	{
		return Point(x + b.x, y + b.y);
	}
	Point operator /(const double& k)const
	{
		return Point(x / k, y / k);
	}
	Point rotate(Point p, double angle)//绕着p点逆时针旋转angle弧度
	{
		Point v = (*this) - 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 s, e;
	Line() {};
	Line(Point _s, Point _e)//求凸包时Line类只需该函数及以上的函数！
	{
		s = _s;
		e = _e;
	}
	bool operator == (Line v)
	{
		return(s == v.s) && (e == v.e);
	}
	void input()
	{
		s.input();
		e.input();
	}
	double length()//求线段长度
	{
		return s.distance(e);
	}
	bool pointonseg(Point p)//点在线段上判断
	{
		return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;
	}
	double dispointtoline(Point p)//点到直线距离
	{
		return fabs((p - s) ^ (e - s)) / length();
	}
	double dispointtoseg(Point p)//点到线段距离
	{
		if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
			return min(p.distance(s), p.distance(e));
		return dispointtoline(p);
	}
};
struct circle
{
	Point p;
	double r;
	circle() {};
	circle(Point _p, double _r)
	{
		p = _p;
		r = _r;
	}
	double area()
	{
		return pi * r * r;
	}
	int relation(Point b)//点和圆关系 0圆外 1圆上 2园内
	{
		double dst = b.distance(p);
		if (sgn(dst - r) < 0)return 2;
		else if (sgn(dst - r) == 0)return 1;
		else return 0;
	}
	int relationseg(Line v)//线段和圆的关系
	{
		double dst = v.dispointtoseg(p);
		if (sgn(dst - r) < 0)return 2;
		else if (sgn(dst - r) == 0)return 1;
		else return 0;
	}
	int relationline(Line v)//直线和圆的关系
	{
		double dst = v.dispointtoline(p);
		if (sgn(dst - r) < 0)return 2;
		else if (sgn(dst - r) == 0)return 1;
		else return 0;
	}
};
struct polygon
{
	int n;
	Point p[maxp];
	Line l[maxp];
	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]);
	}
	int relationpoint(Point q)//判断点和任意多边形关系 3点上 2边上 1内部 0外部
	{
		for (int i = 0; i < n; i++)
			if (p[i] == q)
				return 3;
		getline();
		for (int i = 0; i < n; i++)
			if (l[i].pointonseg(q))
				return 2;
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			int j = (i + 1) % n;
			int k = sgn((q - p[j]) ^ (p[i] - p[j]));
			int u = sgn(p[i].y - q.y);
			int v = sgn(p[j].y - q.y);
			if (k > 0 && u < 0 && v >= 0)cnt++;
			if (k < 0 && v < 0 && u >= 0)cnt--;
		}
		return cnt != 0;
	}
	int relationcircle(circle c)//多边形和圆的关系 2圆完全在多边形内 1圆在多边形内，碰（切）到了多边形边界 0其他
	{
		getline();
		int x = 2;
		if (relationpoint(c.p) != 1)return 0;//圆心不在内部
		for (int i = 0; i < n; ++i)
		{
			if (c.relationseg(l[i]) == 2)return 0;
			if (c.relationseg(l[i]) == 1)x = 1;
		}
		return x;
	}
};

Point p[10], tp;
Line W, R, N, M;
circle C;
polygon G;
double r;

double mj(Point a, Point b, Point c, Point d, int t)
{
	tp = { (a.x + c.x) / 2, (a.y + c.y) / 2 };
	if (C.relation(a) && C.relation(b) && C.relation(c) && C.relation(d))return (a.x - c.x) * (a.x - c.x);
	W = { a,b }; R = { b,c }; N = { c,d }; M = { d,a };
	if (W.dispointtoline(C.p) > r && R.dispointtoline(C.p) > r && N.dispointtoline(C.p) > r && M.dispointtoline(C.p) > r)return 0;
	if (t >= 15 || fabs(a.x - c.x) < 0.02)
	{
		if (C.relation(tp) == 2)return (a.x - c.x) * (a.x - c.x);
		else if (C.relation(tp) == 1)return (a.x - c.x) * (a.x - c.x) / 2;
		else return 0;
	}
	return mj(a, (a + b) / 2, (a + c) / 2, (a + d) / 2, t + 1) + mj((a + b) / 2, b, (b + c) / 2, (a + c) / 2, t + 1) + mj((a + c) / 2, (b + c) / 2, c, (c + d) / 2, t + 1) + mj((a + d) / 2, (a + c) / 2, (c + d) / 2, d, t + 1);
}

int main()
{
	double x, y, xx, yy, xxx, yyy; cin >> x >> y >> xx >> yy >> xxx >> yyy >> r;
	p[0] = Point(xxx, yyy);
	p[1] = Point(x, y);
	p[3] = Point(xx, yy);
	double k = atan2(yy - y, xx - x);
	p[0] = p[0].rotate(Point(0, 0), -k + pi / 4);
	p[1] = p[1].rotate(Point(0, 0), -k + pi / 4);
	p[3] = p[3].rotate(Point(0, 0), -k + pi / 4);
	p[2] = Point(p[3].x, p[1].y);
	p[4] = Point(p[1].x, p[3].y);
	C = circle(p[0], r);
	G.add(p[1]), G.add(p[2]), G.add(p[3]), G.add(p[4]);
	if (G.relationcircle(C) != 0)printf("%.2f", C.area());
	else printf("%.2f", mj(p[1], p[2], p[3], p[4], 0));
}

上面这个吸氧T第一个点，下面跑的飞快，只修改了判断当前递归的正方形是否完全在圆外的那行。

double mj(Point a, Point b, Point c, Point d, int t)
{
	tp = { (a.x + c.x) / 2, (a.y + c.y) / 2 };
	if (C.relation(a) && C.relation(b) && C.relation(c) && C.relation(d))return (a.x - c.x) * (a.x - c.x);
	W = { a,b }; R = { b,c }; N = { c,d }; M = { d,a };
	if (W.dispointtoline(C.p) > r && R.dispointtoline(C.p) > r && N.dispointtoline(C.p) > r && M.dispointtoline(C.p) > r)return 0;
	if (t >= 15 || fabs(a.x - c.x) < 0.02)
	{
		if (C.relation(tp) == 2)return (a.x - c.x) * (a.x - c.x);
		else if (C.relation(tp) == 1)return (a.x - c.x) * (a.x - c.x) / 2;
		else return 0;
	}
	return mj(a, (a + b) / 2, (a + c) / 2, (a + d) / 2, t + 1) + mj((a + b) / 2, b, (b + c) / 2, (a + c) / 2, t + 1) + mj((a + c) / 2, (b + c) / 2, c, (c + d) / 2, t + 1) + mj((a + d) / 2, (a + c) / 2, (c + d) / 2, d, t + 1);
}