bzoj1069 SCOI2007 最大土地面积
2024-09-16 18:03:10
1069: [SCOI2007]最大土地面积
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 2560 Solved: 983
Description
在某块平面土地上有N个点,你可以选择其中的任意四个点,将这片土地围起来,当然,你希望这四个点围成
的多边形面积最大。
Input
第1行一个正整数N,接下来N行,每行2个数x,y,表示该点的横坐标和纵坐标。
Output
最大的多边形面积,答案精确到小数点后3位。
Sample Input
5
0 0
1 0
1 1
0 1
0.5 0.5
0 0
1 0
1 1
0 1
0.5 0.5
Sample Output
1.000
HINT
数据范围 n<=2000, |x|,|y|<=100000
先求个凸包,然后枚举对角线,两边找面积最大的三角形
/*by SilverN*/ #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define ll long long using namespace std; ; struct P{ double x,y; }p[mxn],s[mxn]; ; int n; ; // inline P operator - (P a,P b){ P t; t.x=a.x-b.x; t.y=a.y-b.y; return t; } inline double operator * (P a,P b){ return (a.x*b.y)-(b.x*a.y); } inline double dis(P a,P b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } inline bool operator < (P a,P b){ ])*(b-p[]); )])<dis(b,p[]); ; } // void graham(){ ; int i,j; ;i<=n;i++){ if(p[i].y<p[t].y || (p[i].y==p[t].y && p[i].x<p[t].x))t=i; } swap(p[],p[t]); sort(p+,p+n+); s[++top]=p[];s[++top]=p[]; ;i<=n;i++){ && (p[i]-s[top-])*(s[top]-s[top-])<=) top--; s[++top]=p[i]; } s[top+]=p[]; return; } double solve() { s[top+]=p[]; ; int a,b; ;x<=top;x++) { a=x%top+;b=(x+)%top+; ;y<=top;y++) { !=y&&(s[y]-s[x])*(s[a+]-s[x])>(s[y]-s[x])*(s[a]-s[x])) a=a%top+; !=x&&(s[b+]-s[x])*(s[y]-s[x])>(s[b]-s[x])*(s[y]-s[x])) b=b%top+; ans=max((s[y]-s[x])*(s[a]-s[x])+(s[b]-s[x])*(s[y]-s[x]),ans);//(s[b]-s[x])*(s[y]-s[x])前后颠倒成(s[y]-s[x])*(s[b]-s[x])就会WA,不能理解 } } return ans; } int main(){ scanf("%d",&n); int i,j; ;i<=n;i++){ scanf("%lf%lf",&p[i].x,&p[i].y); } graham(); printf(); ; }
最新文章
- windows中LNK文件打开方式恢复(每日一修(1))
- Collection集合的功能及总结
- iOS OC语言: Block底层实现原理
- 移动端网页fixed布局问题解决方案
- css3制作惊艳hover切换效果
- QC学习三:Excel数据导入导出QC操作流程
- NodeJS学习笔记之MongoDB模块
- 使用astyle格式化代码
- crm维护踩坑记(一)
- MySQL Crash Errcode: 28 - No space left on device
- vscode在vue-cli中按照ESlint自动格式化代码
- 设计模式<;2>;------工厂模式和抽象工厂模式------创建型
- [论文阅读]Object detection at 200 Frames Per Second
- SQL Server - NOLOCK
- Python pyc知识了解
- 内存泄露java.lang.OutOfMemoryError: PermGen space解决方法
- SWAP 简介
- React Native 学习资料
- TCP/UDP端口列表(WIKIpedia)
- 夏天过去了, 姥爷推荐几套来自smashingmagzine的超棒秋天主题壁纸
热门文章
- 使用List的addAll()方法请判空指针
- java 14-2 正则表达式的案例
- PNG文件
- Thread锁 Monitor类、Lock关键字和Mutex类
- 024医疗项目-模块二:药品目录的导入导出-HSSF导入类的学习
- 学习node.js 第4篇 建立一个最小的web聊天系统
- Asp.net通过Jquery操作WebService进行Ajax读写
- 对SharePreference的封装
- Activiti系列:如何让Activiti-Explorer使用sql server数据库
- Windows下虚拟机安装Mac OS X ----- VM12安装Mac OS X 10.11