主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
关于45度角和一次函数的研究报告
最后更新于 2025-07-31 11:10:50
作者
TC_QD
分类
题解
题解
P13511
复制 Markdown
查看原文
删除文章
更新内容
[题目传送门](https://www.luogu.com.cn/problem/P13511) 呃呃(感觉)相当清新的做法( 令 $maxh$ 表示 $N$ 个点中最大的纵坐标, $minh$ 表示最小的纵坐标。 观察样例可以发现,底边上的点的纵坐标要么是 $maxh$ ,要么是 $minh$ 。 还可以发现,其斜边是**系数为 $\pm 1$ 的一次函数上的一条线段**(因为是45度角)。 到了核心部分:接下来我们证明,两种情况下,各自的最优解的两条斜边的 $b$ 一定是最大/小值。 因为 $|b|$ 最大,所以其他点一定在该函数图像下方( $b$ 最大)/上方( $b$ 最小),同时,因为我们已经求出 $maxh$ 和 $minh$ ,所以其构成的三角形一定能够围住所有点。 也就是说,我们让 $b$ 最大的两条直线和 $minh$ 对应,让 $b$ 最小的两条直线和 $maxh$ 对应。 所以,把每个点的 $b1$ ( $k=1$ ), $b2$ ( $k=-1$ )分别处理出来并找到四个最值,再把 $maxh$ 和 $minh$ 分别代入对应的解析式,最后取最小值即为所求。 时间复杂度 $O(n)$ 。 (不过似乎可以构造特殊数据卡爆 `int` ?) ### Cooooode ``` #include<bits/stdc++.h> #define int long long using namespace std; constexpr int e=2e9;//初始值 int n,maxh=-e,minh=e; int mx1=-e,mn1=e,mx2=-e,mn2=e;//b1、b2的最值 struct node{ int x,y,b1,b2;//每个点的信息 }po[100005]; void gb(int i){//计算k=1/k=-1时的b值 int p=po[i].x,q=po[i].y; po[i].b1=q-p; po[i].b2=q+p; return; } signed main(){ cin>>n; for (int i=1;i<=n;i++){ cin>>po[i].x>>po[i].y; maxh=max(maxh,po[i].y);//计算maxh/minh minh=min(minh,po[i].y); gb(i); } for (int i=1;i<=n;i++){ mx1=max(mx1,po[i].b1);//计算四个最值 mn1=min(mn1,po[i].b1); mx2=max(mx2,po[i].b2); mn2=min(mn2,po[i].b2); } cout<<min(mx1+mx2-minh*2,-mn1-mn2+maxh*2);//注意第二个表达式的正负 return 0;//撒花 } ```
正在渲染内容...
点赞
0
收藏
0