计算几何

• 每当约翰将玩具扔进收纳盒中时，确定每个分区中有多少个玩具。

• 判断点在向量的左侧还是右侧，可以用向量叉积的正负来表示。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
const int maxn = 5010;

int N, M;
P a[maxn], b[maxn];
int ans[maxn];

ll cross(ll x1, ll y1, ll x2, ll y2) {
	return x1 * y2 - x2 * y1;
}

ll area(P a, P b, P c) {
	return cross(c.first - a.first, c.second - a.second, b.first - a.first, b.second - a.second);
}
int find(int x, int y) {
	int lb = 0, ub = N;
	while (ub - lb > 0) {
		int mid = (lb + ub) / 2;
		if (area(b[mid], a[mid], { x, y }) < 0) ub = mid;
		else lb = mid + 1;
	}
	return ub;
}

int main() {
	ll x1, y1, x2, y2;
	bool is_first = true;
	while (cin >> N, N) {
		cin >> M >> x1 >> y1 >> x2 >> y2;
		memset(ans, 0, sizeof ans);
		for (int i = 0; i < N; i++) {
			scanf("%lld%lld", &a[i].first, &b[i].first);
			a[i].second = y1, b[i].second = y2;
		}
		a[N] = { x2, y1 }, b[N] = { x2, y2 };
		for (int i = 0; i < M; i++) {
			ll x, y;
			scanf("%lld%lld", &x, &y);
			ans[find(x, y)]++;
		}
		if (!is_first) {
			printf("\n");
		}
		else is_first = false;
		for (int i = 0; i <= N; i++) {
			printf("%d: %d\n", i, ans[i]);
		}
	}
	return 0;
}

• 在二维平面内有 n 条线段，请你编写一个程序，判断是否存在一条直线满足将这 n 条线段投影到该直线上后，所有的投影线段至少具有一个公共点。
• 只要能找到一条穿过所有线段的直线，那么做一条与这条直线垂直的直线，那这条垂直的直线一定满足要求。
• 用旋转直线的方式，那么它必然旋转着旋转着会卡在某一个端点上。换言之，我们只需要找到是否存在过所有线段至少一个端点的直线，就等价于能否找到上述直线。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<double, double> P;
const int maxn = 210;
const double EPS = 1e-8;

int N;
P q[maxn], a[maxn], b[maxn];

bool cmp(double x, double y) {
	if (fabs(x - y) < EPS) return 0;
	else if (x < y) return -1;
	else return 1;
}

int sign(double x) {
	if (fabs(x) < EPS) return 0;
	else if (x < 0) return -1;
	else return 1;
}

double cross(double x1, double y1, double x2, double y2) {
	return x1 * y2 - x2 * y1;
}

double area(P a, P b, P c) {
	return cross(a.first - c.first, a.second - c.second, b.first - c.first, b.second - c.second);
}

bool check() {
	for (int i = 0; i < 2 * N; i++) {
		for (int j = i + 1; j < 2 * N; j++) {
			if (!cmp(q[i].first, q[j].first) && !cmp(q[i].second, q[j].second)) continue;
			bool flag = true;
			for (int k = 0; k < N; k++) {
				if (sign(area(q[i], q[j], a[k])) * sign(area(q[i], q[j], b[k])) > 0) {
                //小心这个判断别写错，想清楚是谁在谁的两侧。
					flag = false;
					break;
				}
			}
			if (flag) return true;
		}
	}
	return false;
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &N);
		for (int i = 0, k = 0; i < N; i++) {
			double x1, y1, x2, y2;
			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			q[k++] = { x1, y1 }, q[k++] = { x2, y2 };
			a[i] = { x1, y1 }, b[i] = { x2, y2 };
		}
		if (check()) printf("Yes!\n");
		else printf("No!\n");

	}
}

• 题意：信用卡是一个矩形，唯四个角作了圆滑处理，使它们都是与矩形的两边相切的 $\frac{1}{4}$ 圆。现在平面上有一些规格相同的信用卡，试求其凸包的周长。注意凸包未必是多边形，因为它可能包含若干段圆弧。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PIQK8Uk4-1686468593882)(C:\Users\DELL\AppData\Roaming\Typora\typora-user-images\image-20210124084732974.png)]

• 圆心角的大小等于两切线的夹角。这个性质要用好。
• 观察可发现，所有圆心构成凸包，加上圆弧长度就是答案。而圆弧的长度是有圆心角之和决定，我们发现圆心角之和等于凸包的外角之和。任意凸多边形外角和是360度。因此凸包长度加上 $2\pi r$ 即可。
• 注意这个题绕中心旋转的处理，是现在原点旋转，再平移。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

#define x first
#define y second

const int maxn = 40010;
const double PI = acos(-1);
typedef pair<double, double> P;
int N, cnt;
P q[maxn];
int stk[maxn], top;
bool used[maxn];

P rotate(P a, double b) {
	return { a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b) };
}

P operator - (P a, P b) {
	return { a.x - b.x, a.y - b.y };
}

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

double area(P a, P b, P c) {
	return cross(b - a, c - a);
}

double get_dist(P a, P b) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}

double andrew() {
	sort(q, q + cnt);
	int top = 0;
	for (int i = 0; i < cnt; i++) {
		while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) {
			if (area(q[stk[top - 1]], q[stk[top]], q[i]) < 0)
				used[stk[top--]] = false;
			else top--;
		}
		stk[++top] = i;
		used[i] = true;
	}
	used[0] = false;
	for (int i = cnt - 1; i >= 0; i--) {
		if (used[i]) continue;
		while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) {
			top--;
		}
		stk[++top] = i;
	}
	double res = 0;
	for (int i = 2; i <= top; i++) {
		res += get_dist(q[stk[i - 1]], q[stk[i]]);
	}
	return res;
}

int main() {
	cin >> N;
	double a, b, r;
	cin >> a >> b >> r;
	a = a / 2 - r, b = b / 2 - r;
	int dx[] = { 1, 1, -1, -1 }, dy[] = { 1, -1, 1, -1 };
	while (N--) {
		double x, y, z;
		scanf("%lf%lf%lf", &x, &y, &z);
		for (int i = 0; i < 4; i++) {
			auto t = rotate({ dx[i] * b, dy[i] * a }, -z);
			q[cnt++] = { t.x + x, t.y + y };
		}
	}
	double res = andrew();
	printf("%.2f\n", res + 2 * PI * r);
}

• 题意：逆时针给出 n 个凸多边形的顶点坐标，求它们交的面积。
• 输入所有点，点两两按顺序形成直线，全部保存在一个数组中，然后对这些点做半平面交。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn = 510;
#define x first
#define y second
typedef pair<double, double> P;

int cnt;
struct Line {
	P st, ed;
}line[maxn];
int q[maxn];  //双端队列
P pg[maxn], ans[maxn];

//（1）先摆上三个常用函数
P operator -(P a, P b) {
	return { a.x - b.x, a.y - b.y };
}
double cross(P a, P b) {
	return a.x * b.y - a.y * b.x;
}
double area(P a, P b, P c) {
	return cross(b - a, c - a);
}

//（2）求直线的交点
P get_line_intersection(P p, P v, P q, P w) {
	auto u = p - q;
	double t = cross(w, u) / cross(v, w);
	return { p.x + v.x * t, p.y + v.y * t };
}
P get_line_intersection(Line a, Line b) {
	return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}

//（3）写直线的比较函数

const double EPS = 1e-8;
int sign(double x) {
	if (fabs(x) < EPS) return 0;
	else if (x < 0) return -1;
	else return 1;
}

int dcmp(double x, double y) {
	if (fabs(x - y) < EPS) return 0;
	else if (x < y) return -1;
	else return 1;
}

double get_angle(const Line& a) {
	//求直线倾斜角 (-PI, PI].
	return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

bool cmp(const Line& a, const Line& b) {
	double A = get_angle(a), B = get_angle(b);
	if (!dcmp(A, B)) return area(a.st, a.ed, b.ed) < 0;
	return A < B;
}

bool on_right(Line& a, Line& b, Line& c) {
	//直线 b 和直线 c 的交点在直线 a 的右侧。
	auto o = get_line_intersection(b, c);
	return sign(area(o, a.st, a.ed)) <= 0;
}
double half_plane_intersection() {

	sort(line, line + cnt, cmp);
	int hh = 0, tt = -1;  //q[hh]表示队头，q[tt]表示队尾， tt - hh + 1 表示队列的大小。
	for (int i = 0; i < cnt; i++) {
		if (i && dcmp(get_angle(line[i]), get_angle(line[i - 1])) == 0) continue;  //角度相同，只保留左边的直线即可。
		//队列多于两个元素时，若队尾两直线交点在新的直线右边，则删除队尾元素。
		while (tt - hh >= 1 && on_right(line[i], line[q[tt]], line[q[tt - 1]])) tt--;
		//同样，对于队头，维护同样的操作。
		while (tt - hh >= 1 && on_right(line[i], line[q[hh]], line[q[hh + 1]])) hh++;
		q[++tt] = i;
	}
	//再用队尾更新队头，用队头更新队尾。
	while (tt - hh >= 1 && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt--;
	while (tt - hh >= 1 && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh++;

	q[++tt] = q[hh];

	int k = 0;
	//注意，最有一个元素是第一个元素，因此要 i < tt;
	for (int i = hh; i < tt; i++) {
		ans[k++] = get_line_intersection(line[q[i]], line[q[i + 1]]);
	}
	double res = 0;
	for (int i = 1; i + 1 < k; i++) {
		res += area(ans[0], ans[i], ans[i + 1]);
	}
	//注意，一定是 res / 2，因为求的是三角形的有向面积，cross 函数求的是两向量构成的平行四边形的有向面积。
	return res / 2;
}

int main() {
	int N, M;
	scanf("%d", &N);
	while (N--) {
		scanf("%d", &M);
		for (int i = 0; i < M; i++) {
			scanf("%lf%lf", &pg[i].x, &pg[i].y);
		}
		for (int i = 0; i < M; i++) {
			line[cnt++] = { pg[i], pg[(i + 1) % M] };
		}
	}
	double res = half_plane_intersection();
	printf("%.3f\n", res);
	return 0;
}

• 在一个二维平面上给定 N 个点，请你画出一个最小的能够包含所有点的圆。圆的边上的点视作在圆的内部。

#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;

#define x first
#define y second

const int maxn = 100010;
const double eps = 1e-12;
const double PI = acos(-1);
typedef pair<double, double> P;
typedef pair<P, P> Line;
int N;
P q[maxn];
//圆的结构体
struct Circle {
	P p;
	double r;
};
int sign(double x) {
	if (fabs(x) < eps) return 0;
	if (x < 0) return -1;
	return 1;
}
int dcmp(double x, double y) {
	if (fabs(x - y) < eps) return 0;
	if (x < y) return -1;
	return 1;
}
P operator -(P a, P b) {
	return { a.x - b.x, a.y - b.y };
}
P operator +(P a, P b) {
	return { a.x + b.x, a.y + b.y };
}
P operator *(P a, double t) {
	return { t * a.x, t * a.y };
}
P operator /(P a, double t) {
	return { a.x / t, a.y / t };
}
double cross(P a, P b) {
	return a.x * b.y - a.y * b.x;
}
double get_dist(P a, P b) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}
//求两直线交点
P get_line_intersection(P p, P v, P q, P w) {
	auto u = p - q;
	double t = cross(w, u) / cross(v, w);
	return p + v * t;
}

//求中垂线
P rotate(P a, double b) {
	return { a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b) };
}
Line get_line(P a, P b) {
	return { (a + b) / 2, rotate(b - a, PI / 2) };
}
//求外接圆
Circle get_circle(P a, P b, P c) {
	auto u = get_line(a, b), v = get_line(a, c);
	auto o = get_line_intersection(u.x, u.y, v.x, v.y);
	return { o, get_dist(o, a) };
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
	random_shuffle(q, q + N);

	Circle c = { q[0] , 0 };
	for (int i = 1; i < N; i++) {
		if (dcmp(c.r, get_dist(c.p, q[i])) < 0) {
			c = { q[i], 0 };
			for (int j = 0; j < i; j++) {
				if (dcmp(c.r, get_dist(c.p, q[j])) < 0) {
					c = { (q[i] + q[j]) / 2, get_dist(q[i], q[j]) / 2 };
					for (int k = 0; k < j; k++) {
						if (dcmp(c.r, get_dist(c.p, q[k])) < 0) {
							//三点确定一个圆
							c = get_circle(q[i], q[j], q[k]);
						}
						
					}
				}
			}
		}
	}
	printf("%.10f\n", c.r);
	printf("%.10f %.10f\n", c.p.x, c.p.y);
	return 0;
}

• 题意：无线网络基站在理想状况下有效信号覆盖范围是个圆形，而无线基站的功耗与圆的半径的平方成正比。增幅仪能够在不增加无线基站功耗的前提下，使得有效信号的覆盖范围在某一特定方向上伸长若干倍。
• 先把所有点旋转（注意与增幅仪旋转方向相反）就相当于椭圆与坐标轴平行了。此题椭圆的方程为 $\frac{x^2}{p^2}+y^2=r^2$. 因此，我们再把所有点的横坐标都变为 $x^{\prime }=\frac{x}{p}$，就变成了典型的最小圆覆盖问题。

代码和上一道题没啥区别，略。

• 题意：输入包括该产品的顶点的个数，以及所有顶点的坐标；请计算出包裹这个产品所需要的材料的最小面积
• 其实就是求三维凸包，通常是一个 $O(n^2)$ 的暴力求法。
• 用逆时针方向三个点维护一个面。加入了随机扰动，防止四个点共面的情况，因此就不用加入近似的判断了，比如 sign 与 dcmp 函数。这样可以有效防止四点共面。

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn = 110;
const double eps = 1e-12;

int N, M; //点的总数，三维凸包面的个数
bool g[maxn][maxn];  //记录每个面是否被照到。g[i][j] 表示 i 和 j 相连的边。
double rand_eps() {
	return ((double)rand() / RAND_MAX - 0.5) * eps;
}

struct Point {
	double x, y, z;
	void shake() {
		x += rand_eps(), y += rand_eps(), z += rand_eps();
	}
	Point operator-(Point t) {
		return { x - t.x, y - t.y, z - t.z };
	}
	Point operator+(Point t) {
		return { x + t.x, y + t.y, z + t.z };
	}
	//点乘
	double operator&(Point t) {    //小心优先级的问题，因为&优先级挺低的。
		return x * t.x + y * t.y + z * t.z;
	}
	//叉乘
	Point operator*(Point t) {
		return { y * t.z - t.y * z, z * t.x - x * t.z, x * t.y - y * t.x };
	}
	double len() {
		return sqrt(x * x + y * y + z * z);
	}
}q[maxn];

struct Plane {
	int v[3];
	Point norm() {
		return (q[v[1]] - q[v[0]]) * (q[v[2]] - q[v[0]]);
	}
	double area() {
		return norm().len() / 2;
	}
	bool above(Point a) {
		return ((a - q[v[0]]) & norm()) >= 0;   //一定要加括号，不然优先级会出问题！
	}
}plane[maxn], np[maxn];  //开一个备份数组

void get_convex_3d() {
	plane[M++] = { 0, 1, 2 };
	plane[M++] = { 2, 1, 0 };
	for (int i = 3; i < N; i++) {
		int cnt = 0;
		for (int j = 0; j < M; j++) {
			bool t = plane[j].above(q[i]);
			if (!t) np[cnt++] = plane[j];
			for (int k = 0; k < 3; k++) {
				g[plane[j].v[k]][plane[j].v[(k + 1) % 3]] = t;
			}
		}
		for (int j = 0; j < M; j++) {
			for (int k = 0; k < 3; k++) {
				int a = plane[j].v[k], b = plane[j].v[(k + 1) % 3];
				if (g[a][b] && !g[b][a]) {   //意味着q[i] 只能照到 plane[j] 的一个面
					np[cnt++] = { a, b, i };
				}
			}
		}
		M = cnt;
		for (int j = 0; j < M; j++) plane[j] = np[j];
	}
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lf%lf%lf", &q[i].x, &q[i].y, &q[i].z);
		q[i].shake();
	}
	get_convex_3d();
	double res = 0;
	for (int i = 0; i < M; i++) {
		res += plane[i].area();
	}
	printf("%.6f\n", res);
	return 0;
}