P3145--题解(鱼币~)

学习编程中的Ben

$题目链接:[USACO16OPEN] Splitting the Field G$

前言:

本蒟蒻第一篇题解, 存在问题的的地方还请各位多多包涵、指出。

核心思路
本题可以简化成在网格图中有 $n$ 个点，让你圈出 $2$ 个矩形，使得这 $2$ 个矩形面积最小。

1.建立矩阵

题目中指出所有坐标都是正数，于是我们可以 $(0, 0)$ 为锚点，从远到近将所有的点排序.再从第一个点开始枚举，将点的序列分为前后两部分。

$$ ans_{i} = S_{1, i} + S_{i + 1, n} $$

这样分可以将所有的点分成离锚点较近的和距离锚点较远的点，易证没有更优的分法。

2.求矩形面积

通过观察，我们可以发现矩形的长就是这些点中 最大的 $x$ 的值 减去 最小的 $x$ 的值，宽是这些点中 最大的 $y$ 的值 减去 最小的 $y$ 的值。

那我们的问题可以转化成求区间内最值

数据范围是 $ 1 \le n \le 50000 $

我们要枚举每一个点，找到每一个点的最大和最小的 $x$ 和 $y$ 的值，所以需要对查找操作进行优化. 这里推荐使用 $RMQ$.不懂戳这儿 $RMQ$简单介绍

注意事项:
1. 我们应该将 $x, y$ 分别排序，取最小值(只对 $x$ 排序 $80$ 分)
2. 不开 $ long~long $ 见祖宗
3. $RMQ$ 要设置初始值
4. 求出 $ans$ 后要用整个矩形的面积减去 $ans$

代码如下:

1. #include <bits/stdc++.h>
   
2. #define int long long
   
3. using namespace std;
   
4. int n, fx[50001][31][2], fy[50001][30][2], ans = 1e20, t, lx, ly, rx, ry;
   
5. struct cow{
   
6.         int x, y;
   
7. }a[50001];
   
8. bool cmp1(cow a, cow b){
   
9.         return a.x < b.x;
   
10. }
    
11. bool cmp2(cow a, cow b){
    
12.         return a.y < b.y;
    
13. }
    
14. inline int read(){
    
15.     int x=0,f=1;
    
16.     char ch=getchar();
    
17.     while(ch<'0' || ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
    
18.     while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    
19.     return x*f;
    
20. }
    
21. void rmq(){
    
22.         for (int i = 0; i <= n; i++){
    
23.                 for (int j = 0; j <= 30; j++){
    
24.                         fx[i][j][0] = fy[i][j][0] = 1e20;
    
25.                 }
    
26.         }
    
27.         for (int i = 1; i <= n; i++) fx[i][0][0] = fx[i][0][1] = a[i].x, fy[i][0][0] = fy[i][0][1] = a[i].y;
    
28.         for (int j = 1; j <= 30; j++){
    
29.                 for (int i = 1; i + (1 << j) - 1 <= n; i++){
    
30.                         fx[i][j][0] = min(fx[i][j - 1][0], fx[i + (1 << j - 1)][j - 1][0]);
    
31.                         fx[i][j][1] = max(fx[i][j - 1][1], fx[i + (1 << j - 1)][j - 1][1]);
    
32.                         fy[i][j][0] = min(fy[i][j - 1][0], fy[i + (1 << j - 1)][j - 1][0]);
    
33.                         fy[i][j][1] = max(fy[i][j - 1][1], fy[i + (1 << j - 1)][j - 1][1]);
    
34.                 }
    
35.         }
    
36. }
    
37. int find(int l, int r){
    
38.         t = log2(r - l + 1);
    
39.         lx = max(fx[l][t][1], fx[r - (1 << t) + 1][t][1]);
    
40.         rx = min(fx[l][t][0], fx[r - (1 << t) + 1][t][0]);
    
41.         ly = max(fy[l][t][1], fy[r - (1 << t) + 1][t][1]);
    
42.         ry = min(fy[l][t][0], fy[r - (1 << t) + 1][t][0]);
    
43.         return (lx - rx) * (ly - ry);
    
44. }
    
45. signed main() {
    
46.         n = read();
    
47.         for (int i = 1; i <= n; i++) a[i].x = read(), a[i].y = read();
    
48.         sort(a + 1, a + 1 + n, cmp1);
    
49.         rmq();
    
50.         for (int i = 1; i < n; i++){
    
51.                 int k = find(1, i), q = find(i + 1, n);
    
52.                 ans = min(ans, k + q);
    
53.         }
    
54.         sort(a + 1, a + 1 + n, cmp2);
    
55.         rmq();
    
56.         for (int i = 1; i < n; i++){
    
57.                 int k = find(1, i), q = find(i + 1, n);
    
58.                 ans = min(ans, k + q);
    
59.         }
    
60.         cout << find(1, n) - ans;
    
61.         return 0;
    
62. }

复制代码

博客食用味更佳: 传送门
去我博客支持一下嘿嘿嘿.毕竟是蒟蒻第一篇题解.管理员还在审核.

@liuhongrun2022 @歌者文明清理员 @～风介～ @zhangjinxuan @不二如是 @柿子饼同学 @陶远航
求评分~(快升级了！！！)

学习编程中的Ben

所以说原来是可以LaTeX的。。。

FishC

你好，鱼油！

你的题目思路基本上是对的，下面我来帮你简洁的解答一下这个问题。

### 核心思路
P3145题目可以简化为在网格图中分割n个点，使得用两个矩形圈出的面积最小。

### 具体步骤
1. **排序**：
   - 由于坐标全是正数，可以以(0, 0)为锚点，对所有点按照某个规则排序（如先按x坐标，再按y坐标排序）。

2. **枚举分割点**：
   - 从第一个点开始，尝试将点的序列分为前后两部分，即前i个点和后n-i个点。

3. **计算矩形面积**：
   - 对每一部分，分别求出所包含点集的最小和最大x值、y值。
   - 矩形面积就等于(最大x - 最小x) * (最大y - 最小y)。

4. **更新最小面积**：
   - 对于每一种划分方法，计算两部分的矩形面积总和，并取其中的最小值。

### 算法实现简要描述

1. def min_area(points):
   
2.     points.sort()  # 根据题意先排序所有点
   
3.    
   
4.     min_total_area = float('inf')
   
5.    
   
6.     for i in range(1, len(points)):
   
7.         left_part = points[:i]
   
8.         right_part = points[i:]
   
9.         
   
10.         # 计算左部分矩形的边界
    
11.         min_x1 = min(point[0] for point in left_part)
    
12.         max_x1 = max(point[0] for point in left_part)
    
13.         min_y1 = min(point[1] for point in left_part)
    
14.         max_y1 = max(point[1] for point in left_part)
    
15.         
    
16.         # 计算右部分矩形的边界
    
17.         min_x2 = min(point[0] for point in right_part)
    
18.         max_x2 = max(point[0] for point in right_part)
    
19.         min_y2 = min(point[1] for point in right_part)
    
20.         max_y2 = max(point[1] for point in right_part)
    
21.         
    
22.         # 计算面积
    
23.         area1 = (max_x1 - min_x1) * (max_y1 - min_y1)
    
24.         area2 = (max_x2 - min_x2) * (max_y2 - min_y2)
    
25.         
    
26.         # 更新最小面积
    
27.         min_total_area = min(min_total_area, area1 + area2)
    
28.    
    
29.     return min_total_area

复制代码

以上算法的时间复杂度为 \(O(n \log n)\)（排序） + \(O(n^2)\)（枚举分割和计算面积），在n较小时是可行的。可以通过更复杂的数据结构优化最小最大值的计算以实现进一步的性能提升。

希望这个回答能帮助你更好地理解和解决这个问题。如果有不清楚的地方，欢迎继续提问！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

很cool的阳

学习编程中的Ben

谢谢啦~@～风介～
等了好久都没几个人回复，评分
现在论坛怪冷清的.以前这种有鱼币的帖子回复率还是挺高的

Wei-Yuanzhe

shuaijun

d

曾热爱这世界

&#128076;

harryhan123

zsy0226

膜拜orz

简柠啦

trinityee

看看

森林格格屋

谢谢

曾热爱这世界

.

考不好不改名

OIer 居然跑到这来发题解

FriedII

看看

XiaoMengXin-1

落芸

XiaoMengXin-1

谢谢鱼币

stumblemodel

没看懂怎么办