【模板】计算几何

  • 开头:
#include<bits/stdc++.h>
using namespace std;
#define Re register int
typedef double dl;

const dl eps = 1e-10;
  • 向量表示:
struct vet
{
	dl x, y;
};
  • 直线表示
struct li
{
	vet a, b;//a为起点,b为向量
};
  • 线段表示
struct li
{
	vet a, b;//a为起点,b为终点
};
  • 基础运算
inline vet operator + (vet x, vet y)//向量+向量
{
	return vet{x.x + y.x, x.y + y.y};
}

inline vet operator - (vet x, vet y)//向量-向量
{
	return vet{x.x - y.x, x.y - y.y};
}

inline vet operator * (vet x, dl y)//向量*某个值
{
	return vet{x.x * y, x.y * y};
}

inline vet operator / (vet x, dl y)//向量/某个值
{
	return vet{x.x / y, x.y / y};
}

inline dl cj(vet x, vet y)//叉积
{
	return x.x * y.y - x.y * y.x;
}

inline dl dj(vet x, vet y)//点积
{
	return x.x * y.x + x.y * y.y;
}
  • 求模长
inline dl len(vet x)
{
	return sqrt(x.x * x.x + x.y * x.y);
}
  • 判断三点是否共线
inline bool check_gx(vet x, vet y, vet z)
{
	return abs(cj(y - x, z - x)) < eps;
}
  • 判断某个点是否在一条有向直线的右侧(左侧同理)
inline bool check_right(li x, vet y)
{
	return cj(y - x.a, x.b) > -eps;
}
  • 两直线求交
inline vet find_id(li x, li y)
{
	dl z = cj(x.a - y.a, y.b) / cj(y.b, x.b);
	return x.a + x.b * z;
}
  • 多边形面积
inline dl get_S()
{
	dl S = 0; 
	for (Re i = 1; i <= n; ++i) S += cj(d[i], d[i > 1 ? i - 1 : n]);//d[i]为多边形按顺时针或逆时针依次经过的顶点坐标,类型为vet
	if (S < 0) S = -S;
	return 0.5 * S;
}
  • \(\mathcal O(log\ n)\)判断一个点是否在一个凸包的内部
inline bool check(vet x)//凸包上的点编号为0~n,c数组为凸包上的每个点代表的坐标向量减去上一个点的坐标向量,其中c[0]为最下面的点中最靠左的点,c[0]没有被处理
{
	x = x - c[0];
	if (cj(x, c[1]) > eps || cj(x, c[n]) < -eps) return 0;
	int l = 2, r = n - 1, s = 1;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (cj(c[mid], x) > -eps) s = mid, l = mid + 1;
		else r = mid - 1;
	}
	return cj(c[s] - x, c[s + 1] - x) > -eps;
}
#include<bits/stdc++.h>
using namespace std;
#define Re register int
typedef double dl;

const int N = 505;
const dl eps = 1e-10;
struct vet
{
	dl x, y;
}q[N];
struct li
{
	vet a, b;
	dl ang;
}d[N];
int n, m, num, l = 1, r, g[N];
dl ans;

inline int read()
{
	char c = getchar();
	int ans = 0;
	bool f = 1;
	while (c < 48 || c > 57)
	{
		if (c == '-') f = 0;
		c = getchar();
	}
	while (c >= 48 && c <= 57) ans = (ans << 3) + (ans << 1) + (c ^ 48), c = getchar();
	return f ? ans : -ans;
}

inline vet operator + (vet x, vet y)
{
	return vet{x.x + y.x, x.y + y.y};
}

inline vet operator - (vet x, vet y)
{
	return vet{x.x - y.x, x.y - y.y};
}

inline vet operator * (vet x, dl y)
{
	return vet{x.x * y, x.y * y};
}

inline dl cj(vet x, vet y)
{
	return x.x * y.y - x.y * y.x;
}

inline li make_line(vet x, vet y)
{
	vet z = y - x;
	return li{x, z, atan2(z.y, z.x)};
}

inline vet find_id(li x, li y)
{
	dl z = cj(x.a - y.a, y.b) / cj(y.b, x.b);
	return x.a + x.b * z;
}

inline bool cmp(li x, li y)
{
	return abs(x.ang - y.ang) > eps ? x.ang < y.ang : cj(y.a - x.a, x.b) > eps;
}

int main()
{
	n = read();
	while (n--)
	{
		m = read();
		for (Re i = 1; i <= m; ++i) q[i].x = read(), q[i].y = read();
		for (Re i = 1; i <= m; ++i) d[++num] = make_line(q[i], q[(i > 1) ? i - 1 : m]);
	}
	sort(d + 1, d + num + 1, cmp);
	for (Re i = 1; i <= num; ++i)
	{
		if (i > 1 && abs(d[i].ang - d[i - 1].ang) < eps && abs(cj(d[i - 1].a - d[i].a, d[i].b)) < eps) continue;
		while (l < r && cj(q[r - 1] - d[i].a, d[i].b) < -eps) --r;
		while (l < r && cj(q[l] - d[i].a, d[i].b) < -eps) ++l;
		if (l <= r && abs(d[i].ang - d[g[r]].ang) < eps)
		{
			li u = d[i], v = d[g[r]];
			if (cj(u.a - v.a, v.b) > eps && cj(v.a - u.a, u.b) > eps)
			{
				printf("0.000");
				return 0;
			}
			--r;
		}
		g[++r] = i;
		if (l < r) q[r - 1] = find_id(d[g[r - 1]], d[i]);
	}
	while (l < r && cj(q[r - 1] - d[g[l]].a, d[g[l]].b) < -eps) --r;
	if (r < l + 2) printf("0.000");
	else
	{
		q[r] = find_id(d[g[l]], d[g[r]]);
		for (Re i = l; i <= r; ++i)
		{
			int u = (i ^ l) ? i - 1 : r, v = (i ^ r) ? i + 1 : l;
			ans += cj(q[i], q[v]);
		}
		if (ans < -eps) ans = -ans;
		printf("%.3lf", 0.5 * ans);
	}
	return 0;
}
上一篇:价值投资第一课程 —— 解读财务报表


下一篇:练习4-3 求给定精度的简单交错序列部分和 (15分)