自动搬运

查看原文

来自洛谷，原作者为

	Vct14 **

搬运于2025-08-24 23:07:19，当前版本为作者最后更新于2025-01-05 10:16:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

搬自本题官方题解。

题意：给出 $N$ 个点，两两连边，以每一条边为直径作圆，求圆的并的面积。

原问题是如果一个点被保护，当且仅当它到某两个点形成的角度大于等于 $90$ 度。

显然可行区域的边界可以视为，使用一个直角去卡这个点集，然后在直角旋转过程中，端点留下的路径。可以看出只保留凸包上的点，不会对本题答案产生任何影响。

使用一个直角进行旋转卡壳，容易证明在旋转过程中，两边卡着的点都是单向移动的。当确定了卡着的两个点的时候，显然可以推出这个直角端点，在旋转的过程中经过的是一段以这两个点的连线作为直径的圆的圆弧。

那么我们将边界分为多段圆弧，并在凸包中任取一点作为中心，然后依次计算每段圆弧与中心形成的图形的面积，之和即为本题答案。

对于每个圆弧与中心形成的图形，是一个弓形与一个三角形，弓形面积可以使用扇形减去对应连向圆心的三角形，而原来的三角形面积可以通过向量叉积计算。

总复杂度 $O(n\log n)$。

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

typedef long double type;
typedef long long ll;
const type pi = acos(-1.0), eps = 1e-9;

type equal(type x, type y = 0.0)
{
	return abs(x - y) < eps;
}
template<class T>
T sqr(T x)
{
	return x * x;
}
struct point
{
	ll x, y;
	point(ll x = 0, ll y = 0): x(x), y(y) {}
	ll lensqr() { return sqr(x) + sqr(y); }
	type len() { return sqrt(lensqr()); }
};
point operator + (const point &a, const point &b)
{
	return point(a.x + b.x, a.y + b.y);
}
point operator - (const point &a, const point &b)
{
	return point(a.x - b.x, a.y - b.y);
}
ll operator * (const point &a, const point &b)
{
	return a.x * b.y - a.y * b.x;
}
ll InnerProduct(const point &a, const point &b)
{
	return a.x * b.x + a.y * b.y;
}

bool compare(const point &a, const point &b)
{
	return a.x == b.x ? a.y < b.y : a.x < b.x;
}
vector<point> ConvexHall(vector<point> p)
{
	sort(p.begin(), p.end(), compare);
	int n = 0;
	vector<point> ans;
	for (int i = 0; i < p.size(); ++i)
	{
		for (;n >= 2 && (ans[n - 1] - ans[n - 2]) * (p[i] - ans[n - 1]) >= 0; --n, ans.pop_back());
		++n; ans.push_back(p[i]);
	}
	for (int i = p.size() - 2, m = n + 1; i >= 0; --i)
	{
		for (;n >= m && (ans[n - 1] - ans[n - 2]) * (p[i] - ans[n - 1]) >= 0; --n, ans.pop_back());
		++n; ans.push_back(p[i]);
	}
	return ans;
}

type X, Y;
struct crossing
{
	type x, y, angle;
	int p1, p2, v;
};
bool cmp(crossing c1, crossing c2)
{
	return c1.angle < c2.angle;
}
int cross(crossing c1, crossing c2)
{
	int x[6] = {c1.p1, c1.p2, c1.v, c2.p1, c2.p2, c2.v};
	sort(x, x + 6);
	return 6 - (unique(x, x + 6) - x);
}


struct fpoint{
	type x,y;
	type len(){
		return sqrt(x*x+y*y);
	}
};
fpoint operator - (fpoint A, fpoint B){
	return (fpoint){A.x - B.x, A.y - B.y};
}
type operator * (fpoint A, fpoint B){
	return A.x*B.y - B.x*A.y;
}
type getS(fpoint A, fpoint B, fpoint C){
	return abs((A-C)*(B-C)/2);
}

type getArea(crossing c1, crossing c2, type Ox, type Oy, type D){
	fpoint O = (fpoint){Ox,Oy};
	fpoint p1 = (fpoint){c1.x, c1.y};
	fpoint p2 = (fpoint){c2.x, c2.y};
	fpoint base = (fpoint){X,Y};

	type l = D * asin(min(sqrt(sqr(c1.x - c2.x) + sqr(c1.y - c2.y)) / D, (type)1));
	type s1 = l * (p1-O).len() / 2;
	return s1 - getS(p1,p2,O) + getS(p1,p2,base);
}

type calc(vector<point> p)
{
//	for (point v: p) printf("(%lld. %lld) -> ", v.x, v.y); puts("");
	int n = p.size() - 1, *id = new int[n + n + 1];
	id[0]=0; 
	p.resize(n + n + 1);
	for (int i = 1; i <= n; ++i) p[i + n] = p[i];
	for (int i = 1; i <= n + n; ++i) id[i] = i % n;
	vector<crossing> C;
	for (int i = 1, j = 1; i <= n; ++i)
	{
		point l = p[i] - p[i - 1];
		if (InnerProduct(p[i + 1] - p[i], l) <= 0)
		{
			C.push_back((crossing){(type)p[i].x, (type)p[i].y, (type)0, id[i - 1], id[i + 1], id[i]});
			j = i + 1;
		}
		else
		{
			for (; InnerProduct(p[j + 1] - p[j], l) > 0; ++j);
			type x = p[i].x + l.x * ((type)InnerProduct(l, p[j] - p[i]) / l.lensqr());
			type y = p[i].y + l.y * ((type)InnerProduct(l, p[j] - p[i]) / l.lensqr());
			C.push_back((crossing){x, y, (type)0, id[i - 1], id[i], id[j]});
		}
	}
	for (int i = n + n - 1, j = i; i >= n; --i)
	{
		point l = p[i] - p[i + 1];
		if (InnerProduct(p[i - 1] - p[i], l) > 0)
		{
			for (; InnerProduct(p[j - 1] - p[j], l) > 0; --j);
			type x = p[i].x + l.x * ((type)InnerProduct(l, p[j] - p[i]) / l.lensqr());
			type y = p[i].y + l.y * ((type)InnerProduct(l, p[j] - p[i]) / l.lensqr());
			C.push_back((crossing){x, y, (type)0, id[i + 1], id[i], id[j]});
		}
		else j = i - 1;
	}
	for (int i = 0; i < n; ++i) X += p[i].x, Y += p[i].y;
	X /= n; Y /= n;
	for (int i = 0; i < C.size(); ++i) C[i].angle = atan2(C[i].y - Y, C[i].x - X);
	sort(C.begin(), C.end(), cmp);
	//for (crossing c: C) printf("(%Lf, %Lf) p1=%d p2=%d v=%d\n", c.x, c.y, c.p1, c.p2, c.v);
	if (cross(C[0], C.back()) < 2)
	{
		if (cross(C[1], C[2]) < 2)
			swap(C[0], C[1]);
		else
			swap(C[C.size() - 1], C[C.size() - 2]);
	}
	C.push_back(C[0]);
	for (int i = 0; i + 1< C.size(); ++i)
		if (cross(C[i], C[i + 1]) < 2) swap(C[i + 1], C[i + 2]);
	type ans = 0;
	for (int i = 0; i + 1 < C.size(); ++i)
	{
		crossing c1 = C[i], c2 = C[i + 1];
		if (cross(c1, c2) < 2) cerr << "FoolMike" << endl, exit(0);
		int id1 = c1.v, id2 = c2.v;
		if (c1.v == c2.v)
		{
			if (c1.p1 > c1.p2) swap(c1.p1, c1.p2);
			if (c2.p1 > c2.p2) swap(c2.p1, c2.p2);
			if (c1.p1 == c2.p1 && c1.p2 == c2.p2) id2 = ((p[c1.p1] - p[c1.v]).lensqr() > (p[c1.p2] - p[c1.v]).lensqr() ? c1.p2 : c1.p1);
		}
		if (id1 == id2) id2 = (c1.p1 == c2.p1 || c1.p1 == c2.p2 ? c1.p1 : c1.p2);
		type Ox = (type)0.5 * (p[id1].x + p[id2].x), Oy = (type)0.5 * (p[id1].y + p[id2].y), D = (p[id1] - p[id2]).len();
		//printf("%d %d\n",id1,id2);
		//printf("len = %Lf, D = %Lf\n", sqrt(sqr(c1.x - c2.x) + sqr(c1.y - c2.y)), D);
		ans += getArea(c1, c2, Ox, Oy, D);
	}
	return ans;
}

int n;

int main()
{
	scanf("%d", &n);
	vector<point> p(n);
	for (int i = 0; i < n; ++i) scanf("%lld%lld", &p[i].x, &p[i].y);
	bool check = true;
	for (int i = 2; i < n; ++i)
		if ((p[i] - p[0]) * (p[1] - p[0]) != 0) check = false;
	if (check)
	{
		point x = p[0];
		for (int i = 1; i < n; ++i)
			if ((p[i] - p[0]).lensqr() > (x - p[0]).lensqr()) x = p[i];
		type ans = 0;
		for (int i = 0; i < n; ++i) ans = max(ans, (p[i] - x).len());
		printf("%.9Lf\n", ans/2 * ans/2 * pi);
		return 0;
	}
	printf("%.9Lf\n", calc(ConvexHall(p)));
	return 0;
}