比较基础的计算几何，但架不住我计几拉吖
One Fourth
思路
先把面积算出来，记为 $s$
然后有一个滑动窗口的技巧，枚举 $l$ ，若当前面积小于四分之一，就让 $r$ 加 $1$ ，计算面积；每次 $l$ 加 $1$ 后面积减小；
因为 $l, r$ 都是单调的，所以是 $O(n)$ 的
代码
一个坑是 abs() 的返回值是 int ，只有 std::abs() 的返回值才可以是任意类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <bits/stdc++.h>
using LL = long long;
const int N = 1e5 + 100;
const LL INF = 8e18;
int n;
LL s = 0, ans = INF, e = 0;
struct Point
{
LL x, y;
Point operator - (Point _t){ return {x - _t.x, y - _t.y}; }
LL operator * (Point _t){ return x * _t.y - y * _t.x; }
} p[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld %lld", &p[i].x, &p[i].y);
for (int i = 2; i < n; ++i) s += std::abs((p[i] - p[1]) * (p[i + 1] - p[1]));
for (int l = 1, r = 2; l <= n; ++l)
{
while (4 * e < s)
{
e += std::abs((p[r] - p[l]) * (p[r % n + 1] - p[l]));
r = r % n + 1;
ans = std::min(ans, std::abs(s - 4 * e));
}
e -= std::abs((p[l] - p[r]) * (p[l % n + 1] - p[r]));
ans = std::min(ans, std::abs(s - 4 * e));
}
printf("%lld", ans);
return 0;
}
|