【2021CCPC桂林】F. Illuminations II

原链接：Problem - F - Codeforces，Illuminations II - 题目 - QOJ.ac

题目大意

给你两个凸多边形，其中大多边形有 $n$ 个顶点，小多边形有 $m$ 个顶点。较小多边形的所有顶点都严格位于较大多边形的内部，因此较小多边形完全严格位于较大多边形的内部。

我们亲爱的朋友 JB 打算在大多边形的内部边界上安装照明装置，以照亮小多边形的一些外部边界。由于犹豫不决，JB 决定在大多边形的内部边界上随机均匀地选择安装照明器的位置，你需要计算小多边形被照亮的边界的预期长度。

题解

由于期望的可加性，我们可以把总期望拆成小多边形每个边的期望相加，把每个边向两侧延长与大多边形交于两个交点。那么由此可以得出，对于每个小多边形边的期望就是：单条边的边长 $\times$ 两个交点之间的线段长度总和 $/$ 大多边形长度总和。这个求区间长度可以用双指针和前缀和来实现，两个交点的移动具有单调性，但是要十分注意细节。线段相交的右端点不能在直线的左边，相交的左端点不能在直线的右边。具体实现起来细节较多，需要注意一下。但是下面的代码在CF上面一直T31，但是在QOJ上面就能AC，实在是未解之谜。此题卡double精度，需要用long double，能用直线相交的函数就用这个，用线段模拟射线尽量不要用。

代码

#include <bits/stdc++.h>
#define endl "\n"
#define No cout << "No\n"
#define Yes cout << "Yes\n"
#define fi first
#define se second
#define int long long
#define double long double
#define DIN freopen("input.txt", "r", stdin);
#define DOUT freopen("output.txt", "w", stdout);
using namespace std;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int N = 2e5 + 50;
const int MOD = 1e9 + 7;

const double eps = 1e-8;
const double PI = acos(-1.0); // 3.1415926...

int dcmp(double x) // 处理精度，判断正负
{
	if (fabs(x) < eps)
		return 0;		   // x == 0 精度范围内的近似相等
	return x > 0 ? 1 : -1; // 返回正负
}

struct point
{
	double x, y;
	bool friend operator<(point a, point b)
	{
		if (a.x != a.y)
			return a.x < b.x;
		return a.y < b.y;
	}
}; // 定义点或向量

struct line
{				// 直线或者线段
	point s, e; // 起点和终点
};
typedef point Vector; // 向量
struct circle
{			  // 圆
	point p;  // 圆心
	double r; // 半径
};

point operator+(point a, point b) { return point{a.x + b.x, a.y + b.y}; }				   //+
point operator-(point a, point b) { return point{a.x - b.x, a.y - b.y}; }				   //-
point operator*(point a, double t) { return point{a.x * t, a.y * t}; }					   // 数乘
point operator*(double t, point a) { return point{a.x * t, a.y * t}; }					   // 数乘
point operator/(point a, double t) { return point{a.x / t, a.y / t}; }					   // 数除
bool operator==(point a, point b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; } // 判断相等
double dot(point a, point b) { return a.x * b.x + a.y * b.y; }							   // 点积
double cross(point a, point b) { return a.x * b.y - a.y * b.x; }						   // 叉积

double side(point a, point b, point c)
{
	return cross((b - a), (c - a));
} // 判断点在直线的哪一侧 大于0在左侧 小于0在右侧

double dis(point a, point b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
} // 两点间的距离

double len(Vector a)
{
	return sqrt(dot(a, a));
} // 向量模长

double angle(Vector a, Vector b)
{
	return acos(dot(a, b) / len(a) / len(b));
} // 两个向量夹角 值域是[0,Pi]

double angle(line a)
{
	return atan2(a.e.y - a.s.y, a.e.x - a.s.x);
} // 极角(-Pi,Pi]

point rotate(point a, double altha)
{
	return point{a.x * cos(altha) - a.y * sin(altha), a.x * sin(altha) + a.y * cos(altha)};
} // 向量的旋转（逆时针旋转）

point norm(point a)
{
	return a / len(a);
} // 求单位向量

point p1[N], p2[N];
int n, m;
double predis[N * 3];

int nxt(int x, int op)
{
	if (op == 1)
		return x == n ? 1 : x + 1;
	else if (op == 2)
		return x == m ? 1 : x + 1;
}

int pre(int x, int op)
{
	if (op == 1)
		return x == 1 ? n : x - 1;
	else if (op == 2)
		return x == 1 ? m : x - 1;
}

bool intersect_segs(point A, point B, point C, point D)
{ // 线段 AB 和线段 CD 是否相交

	double f1 = cross(C - A, B - A), f2 = cross(D - A, B - A); // 第一条线段的两个端点是否在第二条线段的两侧
	double g1 = cross(A - C, D - C), g2 = cross(B - C, D - C); // 第二条线段的两个端点是否在第一条线段的两侧
	return ((f1 <= 0) ^ (f2 <= 0)) && ((g1 <= 0) ^ (g2 <= 0));
}

point segment_intersection(point A, point B, point C, point D)
{ // 求线段 AB 和线段 CD 之间的交点
	Vector AB = B - A;
	Vector CD = D - C;
	double denominator = cross(AB, CD);
	Vector AC = C - A;
	double t = cross(AC, CD) / denominator;
	return A + AB * t;
}

point Intersection_line(point a, point b, point c, point d){ // 直线AB和直线CD的交点  intersection
	point v = b - a, w = d - c, PQ = a - c; // 直接套用公式就ok了
	double t = cross(PQ, w) / cross(w, v);
	return a + t * v;
} //

double calc(int L, int R)
{
	if (L <= R)
		return predis[R] - predis[L];
	else
		return predis[R + n] - predis[L];
}

void solve()
{

	double sum1 = 0, ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		double x, y;
		cin >> x >> y;
		p1[i] = {x, y};
	}
	for (int i = 1; i <= m; ++i)
	{
		double x, y;
		cin >> x >> y;
		p2[i] = {x, y};
	}
	for (int i = 1; i <= n; ++i)
		sum1 += dis(p1[i], p1[nxt(i, 1)]);

	for (int i = 1, p = 1; i <= 3 * n; ++i, p = nxt(p, 1))
		predis[i] = predis[i - 1] + dis(p1[p], p1[nxt(p, 1)]);

	for (int i = 1, L = 1, R = 1; i <= m; ++i) // i内层 L,R外层
	{
		Vector v = p2[nxt(i, 2)] - p2[i];
		// line AB = {p2[i], p2[i] + v * (1e60)}, BA = {p2[nxt(i, 2)], p2[nxt(i, 2)] - v * (1e60)};
		line AB = {p2[i], p2[nxt(i, 2)]}, BA = {p2[nxt(i, 2)], p2[i]};
		if (i == 1)
		{
			while (1)
			{
				bool flag = cross(AB.e - AB.s, p1[R] - AB.s) < 0;
				if (!flag)
					R = nxt(R, 1);
				else
					break;
			}
		}
		while (1)
		{
			bool flag = cross(AB.e - AB.s, p1[nxt(R, 1)] - AB.s) > 0;
			if (!flag)
				R = nxt(R, 1);
			else
				break;
		}
		if (i == 1)
			L = nxt(R, 1);
		while (1)
		{
			bool flag = cross(AB.e - AB.s, p1[nxt(L, 1)] - AB.s) <= 0;
			if (!flag)
				L = nxt(L, 1);
			else
				break;
		}
		point pL = segment_intersection(BA.s, BA.e, p1[L], p1[nxt(L, 1)]);
		point pR = segment_intersection(AB.s, AB.e, p1[R], p1[nxt(R, 1)]);
		double res1 = calc(L, pre(R, 1));
		double res2 = dis(pL, p1[nxt(L, 1)]);
		double res3 = dis(pR, p1[R]);

		double res4 = dis(p2[i], p2[nxt(i, 2)]);
		ans += res4 * (res1 + res2 + res3) / sum1;
	}
	cout << fixed << setprecision(18) << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	// DIN;
	// DOUT;

	int T = 1;
	// cin >> T;
	while (T--)
		solve();
	// cerr << "Time:" << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
	return 0;
}