首页 > 其他分享 >[题解]P4166 [SCOI2007] 最大土地面积

[题解]P4166 [SCOI2007] 最大土地面积

时间:2024-07-20 21:54:12浏览次数:17  
标签:int 题解 top cross st P4166 vec 顶点 SCOI2007

P4166 [SCOI2007] 最大土地面积

解法\(1\) - \(O(n^2)\)

我们运用调整法,可以证明这个四边形的\(4\)个顶点一定都在凸包的顶点上,具体来说:

\(\textbf{Proof:}\)
首先我们知道,凸包内,到某条直线距离最大的点一定包括\(1\)个顶点。
接下来我们考虑一个凸包内的四边形:

我们过它的对角线做一条直线\(JL\),然后我们就根据上面的结论知道,到\(JL\)距离最大的点一定是凸包的某一个顶点。因此经过调整,把\(M\)和\(K\)都调整到顶点的位置,距离增大了,自然面积也增大。

同理,一直调整到所有四边形顶点都在凸包的顶点上,我们就证明了“不是所有顶点都在凸包顶点上的四边形,面积一定不是最大”,即证明了“面积最大的四边形一定所有顶点都在凸包的顶点上”。\(\color{#f0f0f0}\textbf{Q.E.D.}\)

接下来我们就可以枚举凸包的顶点来解决了,但最暴力的方法\(O(n^4)\)会超时,想想怎么优化。

受旋转卡壳的启发,我们想到枚举一条对角线,然后找\(2\)个离这条对角线最远的点,分别位于对角线的两侧。和旋转卡壳相同地,这一步也是可以用双指针的思想优化的。

#1
#include<bits/stdc++.h>
#define nxtnode(x) (x%top+1)
#define N 2010
using namespace std;
struct vec{
	double x,y;
	vec operator+(vec b){return {x+b.x,y+b.y};}
	vec operator-(vec b){return {x-b.x,y-b.y};}
}a[N];
bool cmp(vec a,vec b){return a.x==b.x?a.y<b.y:a.x<b.x;}
double cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
int n,st[N],top;
bool vis[N];
double ans;
void convex_hull(){
	sort(a+1,a+1+n,cmp);
	memset(vis,0,sizeof vis);
	st[top=1]=1;
	for(int i=2;i<=n;i++){
		while(top>1&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0){
			vis[st[top--]]=0;
		}
		vis[i]=1,st[++top]=i;
	}
	int tmp=top;
	for(int i=n-1;i>=1;i--){
		if(vis[i]) continue;
		while(top!=tmp&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0){
			vis[st[top--]]=0;
		}
		vis[i]=1,st[++top]=i;
	}
	top--;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	convex_hull();
	int p1,p2;
	for(int i=1;i<top;i++){
		p1=p2=i;
		for(int j=i+1;j<=top;j++){
			while(cross(a[st[j]]-a[st[i]],a[st[nxtnode(p1)]]-a[st[i]])>=cross(a[st[j]]-a[st[i]],a[st[p1]]-a[st[i]])){
				p1=nxtnode(p1);
			}
			while(cross(a[st[j]]-a[st[i]],a[st[nxtnode(p2)]]-a[st[i]])<=cross(a[st[j]]-a[st[i]],a[st[p2]]-a[st[i]])){
				p2=nxtnode(p2);
			}
			ans=max(ans,cross(a[st[j]]-a[st[i]],a[st[p1]]-a[st[i]])-cross(a[st[j]]-a[st[i]],a[st[p2]]-a[st[i]]));
		}
	}
	cout<<fixed<<setprecision(3)<<fabs(ans)/2<<"\n";
	return 0;
}

解法\(2\) - \(O(n\log n)\)

进一步分析,我们可以发现,这个面积最大的四边形的对角线一定是对踵点的连线。

\(\textbf{Proof:}\)
我们假设对角线不全是对踵点的连线:

连接\(CG\),则一定能找到到\(CG\)上面离它更远的点,使得面积更大。

此时\(J\)和\(E\)都离\(CG\)最远,无法继续调整,它们是对踵点。\(C,G\)也是对踵点。

所以我们可以想到一个\(O(n)\)的做法来完成这一过程。

仅需枚举一个顶点\(U\),然后找到它的对踵点\(V\),再找到\(UV\)两侧,离\(UV\)最远的两点\(A,B\)。每次更新答案即可。

根据\(U\)找\(V\)可以用双指针的思想来优化,和旋转卡壳枚举点的做法相似。相应地,我们发现线段\(UV\)是按一个方向旋转的,所以\(A,B\)的枚举也可以双指针。

注意第\(1\)个步骤如果出现共线的情况,两个点都需要考虑,不过注意顺序,否则不能保证\(UV\)按一个方向旋转。

这一步骤是\(O(n)\)的,加上凸包的\(O(n\log n)\),总时间复杂度\(O(n\log n)\)。

#include<bits/stdc++.h>
#define nxtnode(x) (x%top+1)
#define N 50010
using namespace std;
struct vec{
	double x,y;
	vec operator+(vec b){return {x+b.x,y+b.y};}
	vec operator-(vec b){return {x-b.x,y-b.y};}
	int squalen(){return x*x+y*y;}
}a[N];
bool cmp(vec a,vec b){return a.x==b.x?a.y<b.y:a.x<b.x;}
double cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
int n,st[N],top;
double ans;
void convex_hull(){
	sort(a+1,a+1+n,cmp);
	st[top=1]=1;
	for(int i=2;i<=n;i++){
		while(top>1&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
			top--;
		st[++top]=i;
	}
	int tmp=top;
	for(int i=n-1;i>=1;i--){
		while(top!=tmp&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>=0)
			top--;
		st[++top]=i;
	}
	top--;
}
void modify(int i,int j,int &k,int &l){//k从i开始,l从j开始
	double tk,tl;
	while(cross(a[st[j]]-a[st[i]],a[st[nxtnode(k)]]-a[st[i]])>=(tk=cross(a[st[j]]-a[st[i]],a[st[k]]-a[st[i]])))
		k=nxtnode(k);
	while(cross(a[st[i]]-a[st[j]],a[st[nxtnode(l)]]-a[st[j]])>=(tl=cross(a[st[i]]-a[st[j]],a[st[l]]-a[st[j]])))
		l=nxtnode(l);
	ans=max(ans,(tk+tl)/2);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	convex_hull();//顺时针
	int j=2,k=1,l=2;
	for(int i=1;i<=top;i++){
		double t;
		while((t=cross(a[st[nxtnode(i)]]-a[st[i]],a[st[nxtnode(j)]]-a[st[j]]))<0)
			j=nxtnode(j);
		modify(i,j,k,l);
		if(t==0) modify(i,nxtnode(j),k,l);
	}
	cout<<fixed<<setprecision(3)<<ans<<"\n";
	return 0;
}

标签:int,题解,top,cross,st,P4166,vec,顶点,SCOI2007
From: https://www.cnblogs.com/Sinktank/p/18311437

相关文章

  • ABC 363 E - Sinking Land 题解
    用一个优先队列维护和海相邻的位置,每次海面上升就判断一下队列中海拔最低的那个位置会不会被淹没,如果会,就删除,同时它上下左右的位置也是和海相邻的(或者就在海里),把它们加进优先队列里,记得判断一下加入的格子曾经有没有被加入过队列,不要加重复了。点击开DconstintN=1099;int......
  • ABC 363 F - Palindromic Expression 题解
    下文中提到的数字都不包含0,注意把含0的数字特判掉。反转指各个数位倒过来,比如114514反转过后就是415411。注意到,答案一定是这样:数列\(a\)的各个数字相乘,乘以一个回文,再把数列\(a\)倒过来,每个数反转,再相乘。比如:2*57*184481*75*2,其中的数列\(a\)就是:257,中间的回文......
  • Python学习笔记39:进阶篇(二十八)pygame的使用之按键映射及按键失效问题解决
    前言基础模块的知识通过这么长时间的学习已经有所了解,更加深入的话需要通过完成各种项目,在这个过程中逐渐学习,成长。我们的下一步目标是完成pythoncrashcourse中的外星人入侵项目,这是一个2D游戏项目。在这之前,我们先简单学习一下pygame模块。私信我发送消息python资料,......
  • CF819B Mister B and PR Shifts 题解
    题目传送门前置知识权值树状数组及应用解法由[ABC351F]DoubleSum的套路,尝试展开绝对值及\(\min,\max\)。将式子拆开有\(\begin{aligned}&\min\limits_{k=0}^{n-1}\{\sum\limits_{i=1}^{n-k}|a_{i}-(i+k)|+\sum\limits_{i=n-k+1}^{n}|a_{i}-(i-(n-k))|\}\\&=\min......
  • WebGoC题解(11) 627.传声(2019NHOI小乙)
    题目描述 小C节日旅游来到一个农场。农场主John和n个奶牛站在一条水平线上。牛的传递消息是依靠“吼”,牛的吼叫声最远可以传递的距离是50。农场主John首先通知最左边的第一条奶牛(一定会通知),然后奶牛就开始向后吼叫,后面的奶牛如果能听到(和前面吼叫的奶牛距离不超过50),就继续向......
  • 2064:【例2.1】交换值 题解
    题目链接题目描述输入两个正整数\(a\)和\(b\),试交换\(a\)、\(b\)的值(使\(a\)的值等于\(b\),\(b\)的值等于\(a\))。解题思路该题有很多种方法,例如:直接输出\(b\)和\(a\)(偷鸡方法)使用algorithm库的swap函数使用额外变量辅助位运算\(......\)但这道题目放在"运算符和表达式"......
  • CF906C Party题解
    今天来水一波题解……理解题意由于题目意思讲得很清楚,就因为懒惰直接复制了……给你一堆一对对的关系,然后每一个关系对代表两个人认识。然后你每次可以选择一个人i,让i认识的所有人都相互认识,即i把介绍自己所有的朋友给其他人。然后现在问你最少需要选择多少个这样的i,使得所有的......
  • 1005:地球人口承载力估计 题解
    题目链接题目描述假设地球上的新生资源按恒定速度增长。照此测算,地球上现有资源加上新生资源可供\(x\)亿人生活\(a\)年,或供\(y\)亿人生活\(b\)年。为了能够实现可持续发展,避免资源枯竭,地球最多能够养活多少亿人?解题思路经典的牛吃草问题,只是换了一个问法而已。可以戳这里,也......
  • openwrt之luci界面开发------问题解析
    查阅视频:我取不来名字的https://space.bilibili.com/320467466在openwrt的luci界面开发中,用到的这个E()函数,其功能是在网页界面创建各种各种视图效果,如按钮,文字等等。其原函数:functionE(){    returnL.dom.create.apply(L.dom,arguments)}这个E()函数定义实......
  • python3 安装Crypto包 出现No module named ‘Crypto‘和No module named ‘Crypto.Ut
       pycrypto、pycrytodome和crypto是一个东西,crypto在python上面的名字是pycrypto,它是一个第三方库,但是已经停止更新三年了,所以不建议安装这个库;这个时候pycryptodome就来了,它是pycrypto的延伸版本,用法和pycrypto是一模一样的;所以,我现在告诉大家一种解决方法--直接安装:pipin......