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

news/2025/2/19 4:33:18/

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;一般的题目只是求最短路…