#Graham算法+决策单调性#[luogu P4166] [SCOI2007]最大土地面积

news/2024/4/21 1:45:00/

Title

https://www.luogu.com.cn/problem/P4166


Solution

先求凸包,然后枚举点 i i i,然后对于点 j j j得到的 i i i j j j(有序)中间的点,以及 j j j i i i(有序)中间的点,都是单调的

  • 先用 G r a h a m Graham Graham算法求凸包
  • 然后枚举四边形的对角线,剩下的两个点 a , b a,b a,b可以根据旋转卡壳的思想巧妙得到,因为决策单调性,每次枚举下一个 j j j时, a , b a,b a,b最远点可以从这次的位置继续同向枚举。
  • 时间复杂度 O ( N l o g 2 N + N 2 ) ≈ O ( N 2 ) O(Nlog_{2}N+N^2) \approx O(N^2) O(Nlog2N+N2)O(N2)

Code

#include<cstdio> 
#include<algorithm>
#include<cmath>
using namespace std; 
const int maxn=2005; 
double ans=0;
struct point{double x,y; point operator - (point&s){return (point){x-s.x,y-s.y};}
}P[maxn],t[maxn];
double operator *(point a,point b){return a.x*b.y-b.x*a.y; 
}
int n,sta[maxn],top; 
inline double dist2(point P1,point P2){return (P1.x-P2.x)*(P1.x-P2.x)+(P1.y-P2.y)*(P1.y-P2.y); 
}
inline bool judgeOnLeft(point p0,point p1,point p2){double s=(p1-p0)*(p2-p0); return s<0||(s==0&&dist2(p1,p0)>=dist2(p2,p0)); 
}
inline bool cmp(point p1,point p2){double s=(p1-P[1])*(p2-P[1]); return s<0||(s==0&&dist2(p1,P[0])>=dist2(p2,P[0])); 
}
inline int Graham(){sort(&P[2],&P[n+1],cmp); P[n+1]=P[1]; sta[1]=1; sta[2]=2; top=2; for(int i=3;i<=n+1;i++){while(top>1&&judgeOnLeft(P[sta[top-1]],P[i],P[sta[top]])) top--; sta[++top]=i; }top--;return top;
} 
inline double solve(){if (n<2) return 0; sta[n+1]=sta[1]; for(int i=1;i<=n+1;i++) t[i]=P[sta[i]]; for(int i=1;i<=n;i++){int a=i,b=i+1; for(int j=i;j<=n;j++){while ((t[j]-t[i])*(t[a+1]-t[i])-(t[j]-t[i])*(t[a]-t[i])>0) a=a%n+1; while ((t[b+1]-t[i])*(t[j]-t[i])-(t[b]-t[i])*(t[j]-t[i])>0) b=b%n+1; ans=max(ans,(t[j]-t[i])*(t[a]-t[i])+(t[b]-t[i])*(t[j]-t[i])); }}return ans/2; 
}
int main(){scanf("%d",&n); int First=1; for(int i=1;i<=n;i++) {scanf("%lf%lf",&P[i].x,&P[i].y); if (P[i].x<P[First].x||(P[i].x==P[First].x&&P[i].y<P[First].y)) First=i; 	}swap(P[First],P[1]); n=Graham(); return 0&printf("%.3lf\n",solve()); 
}

http://www.ppmy.cn/news/243428.html

相关文章

题解 luoguP4166 【[SCOI2007]最大土地面积】

传送门 这里补充一下三分的做法。 首先 n 2 n^2 n2枚举对角线&#xff0c;然后我们要算的是在对角线左边最大的三角形和对角线右边最大的三角形。 显然如果我们任选一侧&#xff0c;从对角线的一个顶点到另一个顶点依次计算&#xff0c;三角形的面积肯定是先增大后减小的&am…

bzoj4166 月宫的符卡序列

题目大意输入格式输出格式样例 样例输入样例输出样例说明 题解 代码很丑 题目大意 给定一个包含26个小写字母的字符串&#xff0c;字符从0开始标号。一个子串a的价值定义为&#xff1a;a在S中的所有出现位置中点的异或值。(规定&#xff1a;若a出现在s[l……r],那么a的中点为…

洛谷4166 最大土地面积(计算几何)

有毒。。。。 【题目分析】 首先讲一波错误的想法&#xff08;来自wcr dalao&#xff09; 为什么要去找最远点对呢&#xff1f;反例太好找了啊&#xff01; 好的讲讲正解&#xff0c;首先要找最大面积&#xff0c;肯定要在凸包上去找四个点&#xff08;证明等我思考出来就更传送…

luogu4166 最大土地面积 (旋转卡壳)

首先这样的点一定在凸包上 然后旋转卡壳就可以 具体来说&#xff0c;枚举对角线的一个端点&#xff0c;另一个端点在凸包上转&#xff0c;剩下两个点就是一个叉积最大一个最小&#xff0c;而这两个点也是跟着转的 所以是$O(N^2)$ 1 #include<bits/stdc.h>2 #include<t…

hdu~4166~Robot Navigation

此题用的广搜加记忆化&#xff0c;一开始没考虑方向&#xff0c;测试数据都过不了&#xff0c;在队友的提醒下才发现&#xff0c;改了之后广搜过了&#xff0c;深搜却错了&#xff0c;调了无数个小错误之后&#xff0c;终于过了测试数据&#xff0c;汗啊&#xff01;&#xff0…

bzoj4166 月宫的符卡序列(manacher+链状双hash)

分析&#xff1a; 网上的题解少之又少&#xff0c;而且都是dalao码风&#xff0c;所以只能自力更生了 仔细分析一下&#xff0c;这道题就是求解本质不同的回文串以及出现位置 由于字符串比较长&#xff0c;我们需要用manacher算法 在manacher算法中&#xff0c;只有发生了扩…

【洛谷 P4166】 [SCOI2007]最大土地面积(凸包,旋转卡壳)

题目链接 又调了我两个多小时巨亏 直接\(O(n^4)\)枚举4个点显然不行。 数据范围提示我们需要一个\(O(n^2)\)的算法。 于是\(O(n^2)\)枚举对角线&#xff0c;然后在这两个点两边各找一个点使其和对角线构成的三角形面积最大&#xff0c;也就是叉积的绝对值最大。显然具有单调性&…

HDU 4166 BNU 32715 Robot Navigation (记忆化bfs)

题意&#xff1a;给一个二维地图&#xff0c;每个点为障碍或者空地&#xff0c;有一个机器人有三种操作&#xff1a;1、向前走&#xff1b;2、左转90度&#xff1b;3、右转90度。现给定起点和终点&#xff0c;问到达终点最短路的条数。 思路&#xff1a;一般的题目只是求最短路…

P4166 [SCOI2007]最大土地面积

传送门 首先&#xff0c;四边形的四个点肯定都在凸包上&#xff08;别问我为什么我也不知道&#xff0c;感性理解一下好了&#xff09; 那么我们可以求出凸包之后\(O(n^4)\)暴力枚举&#xff0c;据说在随机数据下凸包上的点只有\(O(logn)\)个可过 然而出题人大大的没有良心&…

HDU 4166 Robot Navigation

题意&#xff1a; 一个机器人走迷宫 每一秒要么转向要么前进 问 最少时间的情况下有几种方案 思路&#xff1a; 记忆化搜索即可 简单bfs 代码&#xff1a; #include<cstdio> #include<iostream> #include<cstring> #include<string> #include&…

HDU4166【BFS】

题意&#xff1a; 给你一幅图&#xff0c;给你起点和终点&#xff0c;再给你机器人所面对的方向&#xff0c;机器人可以左转90&#xff0c;右转90&#xff0c;向前进一格&#xff0c;每种操作都是1秒&#xff0c;,求起点和终点最少花费下的路径条数&#xff0c;方案数&#xf…

[回文自动机 Manacher] BZOJ4166: 月宫的符卡序列

hash被卡… 本来以为是回文自动机裸题 发现fail树上一条链的节点表示的回文子串的中点是不一样的… 不过回文树上的链是一样的 那么用建出回文树&#xff08;我用回文自动机建的&#xff0c;manacher建不知道为什么WA了&#xff09;&#xff0c;然后找到以每个点为中点的最…

【BZOJ4166】月宫的符卡序列 Manacher+hash

【BZOJ4166】月宫的符卡序列 题解&#xff1a;题倒不难&#xff0c;就是有点恶心。 首先学习回文串的时候一定学到了这样一个结论&#xff1a;一个长度为n的串的本质不同的回文子串数量不超过n个。 那么我们就可以试图将所有回文串的价值都计算出来&#xff0c;这就需要我们先计…

洛谷P4166 [SCOI2007]最大土地面积

将四边形拆成两个三角形。旋转卡壳经典题。 #include <bits/stdc.h> using namespace std; typedef long long LL; typedef int lint; const int maxn 2001; const double eps 1e-12; const double PI acos(-1.0); int sgn(double x) {if(fabs(x) < eps)return 0;…

BZOJ 1069 Luogu P4166 最大土地面积 (凸包)

题目链接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id1069 (luogu)https://www.luogu.org/problemnew/show/P4166 题解: 水题&#xff0c;凸包极角排序之后枚举凸四边形对角线\(i,j\)然后找面积最大的点\(k\)&#xff0c;\(k\)随着\(i,j\)是单调的 但是有个易错…

Android中的Intent(显示隐式)

Android中的Intent(显示&隐式) 显示Intent 显示Intent是明确目标Activity的类名 通过Intent(Context packageContext, Class<?> cls)构造方法Intent intent new Intent(this, SecondActivity.class) startActivity(intent);通过Intent的setComponent()方法Componen…

NLP的idea,看了就能水一篇论文

1.问题 在中文情感分析任务中,已有方法仅从单极、单尺度来考虑情感特征&#xff0c;无法充分挖掘和利用情感特征信息&#xff0c;模型性能不理想。 单级单尺度&#xff1a;只从一个方面学习文本的特征 多级多尺度&#xff1a;应该是分别从不同方面学习文本的特征&#xff0c…

一键提升分辨率,呈现更清晰、更细腻的视觉盛宴

牛学长视频修复工具是一款使用AI技术对你的视频分辨率就行调整放大清晰的软件&#xff0c;最高支持8K超高清。 现如今&#xff0c;视频成为人们记录生活、表达创意的重要方式之一。然而&#xff0c;我们常常遇到一个问题&#xff1a;旧有的视频素材分辨率低&#xff0c;画质模…

priority_queue的模拟实现和仿函数

priority_queue模拟 首先查看源代码&#xff0c;源代码就在queue剩下的部分中 push_heap是STL库中的堆算法&#xff0c;STL库中包装有支持堆的算法&#xff0c;在algorithm.h中&#xff1a; 只要不断用堆的形式插入数据&#xff0c;就会形成堆。 priority_queue模拟——初版 pr…

网络协议——STP协议是什么?是如何实现的?

作者&#xff1a;Insist-- 个人主页&#xff1a;insist--个人主页 作者会持续更新网络知识和python基础知识&#xff0c;期待你的关注 目录 一、STP协议是什么 二、为什么需要STP协议 三、STP的实现过程 ​编辑 1、选举跟桥 2、给非跟桥交换机选举跟端口 3、给每个网段选…