CF611G New Year and Cake 题解

CF611G New Year and Cake

题意

• 给定一个 $n$ 个顶点的严格凸多边形。
• 要求 $\frac{n(n-3)}2$ 个由对角线将多边形割成两个部分的面积差 $\times 2$ 之和。
• $n \le 5 \times 10^5$，答案对 $10^9+7$ 取模。

题解

双指针扫一遍，动态维护对角线隔开的最大面积以及面积对答案的贡献和，其中贡献需要利用叉积的分配率维护有贡献的向量和。

注意本题根据写法不同可能需要开 unsigned long long，但同时需要对答案取模，因此细节很多。

代码

struct Po {
	int x, y;
	inline Po &operator -= (Po o) { return x -= o.x, y -= o.y, *this; }
	inline friend Po operator - (Po a, Po b) { return a -= b; }
	inline friend ll operator % (Po a, Po b) { return 1ll * a.x * b.y - 1ll * a.y * b.x; }
};

inline pair< modint, modint > &operator += (pair< modint, modint > &a, Po b) {
	return a.fi += (b.x % P + P) % P, a.se += (b.y % P + P) % P, a;
}

inline modint operator % (pair< modint, modint > a, Po b) {
	return a.fi * ((b.y % P + P) % P) - a.se * ((b.x % P + P) % P);
}

inline pair< modint, modint > operator * (modint a, Po b) {
	return mp(a * ((b.x % P + P) % P), a * ((b.y % P + P) % P));
}

inline pair< modint, modint > &operator -= (pair< modint, modint > &a, pair< modint, modint > b) {
	return a.fi -= b.fi, a.se -= b.se, a;
}

const int N = 5e5 + 7;
int n, cnt;
Po a[N];
modint ans, o;
pair< modint, modint > p;
ul s, m;

int main() {
	rd(n);
	for (int i = 0; i < n; i++) rd(a[i].x), rd(a[i].y);
	for (int i = 2; i < n; i++) s += (a[i] - a[0]) % (a[i-1] - a[0]);
	for (int i = 0, j = 0; i < n; i++) {
		while (1) {
			int k = (j + 1) % n;
			ul w = (a[k] - a[i]) % (a[j] - a[i]);
			if (2 * (m + w) >= s) {
				if (2 * (m + w) == s) ++cnt;
				break;
			}
			o += (m += w) % P;
			p += a[k] - a[i];
			j = k;
		}
		ans -= o * 2;
		int k = (i + 1) % n;
		m -= (a[j] - a[i]) % (a[k] - a[i]);
		o -= p % (a[k] - a[i]);
		p -= (modint)((j - i + n) % n) * (a[k] - a[i]);
	}
	ans += (modint)((1ll * n * (n - 3) - cnt) / 2 % P) * (modint)(s % P);
	print(ans);
	return 0;
}