求点集中面积最大的三角形...显然这个三角形在凸包上...

但是旋转卡壳一般都是一个点卡另一个点...这种要求三角形的情况就要枚举底边的两个点 卡另一个点了...

随着底边点的递增, 最大点显然是在以l(i,j)为底边进行卡壳旋转

但分析了一下这种卡壳的复杂度到了O(n^2) 感觉不太靠谱...不知道有没有更强的方法...我感觉两个点卡的时候都是凸函数...不是很好卡的样子...如果我想到了我再更新这贴...

/********************* Template ************************/
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std; #define EPS 1e-8
#define MAXN 100005
#define MOD (int)1e9+7
#define PI acos(-1.0)
#define INF ((1LL)<<50)
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define BUG cout<<"BUG! "<<endl
#define LINE cout<<"------------------"<<endl
#define L(t) (t << 1)
#define R(t) (t << 1 | 1)
#define Mid(a,b) ((a + b) >> 1)
#define lowbit(a) (a & -a)
#define FIN freopen("in.txt","r",stdin)
#pragma comment (linker,"/STACK:102400000,102400000") // typedef long long LL;
// typedef unsigned long long ULL;
// typedef __int64 LL;
// typedef unisigned __int64 ULL;
// int gcd(int a,int b){ return b?gcd(b,a%b):a; }
// int lcm(int a,int b){ return a*b/gcd(a,b); } /********************* F ************************/
struct POINT{
double x,y;
POINT(double _x = , double _y = ):x(_x),y(_y){};
void show(){
cout<<x<<" "<<y<<endl;
}
};
POINT p[MAXN],s[MAXN];
double dist(POINT p1,POINT p2){
return((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y));
}
double multiply(POINT sp,POINT ep,POINT op){
return (sp.x-op.x) * (ep.y-op.y) - (ep.x-op.x) * (sp.y-op.y);
}
bool ptcmp(POINT a,POINT b){ // 极角排序cmp p[]为全局变量
if(multiply(a,b,p[]) == ) return dist(p[],a) < dist(p[],b);
return (multiply(a,b,p[]) > );
}
int Graham_scan(POINT p[],POINT s[],int n){ // 返回凸包点的个数(修改版处理共线,无凸包)
int i,k = ,top = ;
for(i = ; i < n ; i++) // 取y最小且x最小的点为凸包起点
if((p[i].y < p[k].y) || ((p[i].y == p[k].y) && (p[i].x < p[k].x)))
k = i;
swap(p[],p[k]); // 起点设置为p[0]
if(n == ) { // 只有两个点不构成凸包的特判
s[] = p[];
s[] = p[];
return ;
}
sort(p+,p+n,ptcmp); // 极角排序
for(i = ; i < ; i++)
s[i] = p[i]; // 前三个点入栈
if(n == && multiply(s[],s[],s[]) != ) return ;// 解决三个点且不共线的bug...
while(multiply(s[],s[top],s[top-]) == && i < n){ // 前三个点的共线特判
s[top-] = s[top];
s[top] = p[i++];
}
if(i == n){ //所有点都共线的特判
s[] = s[top];
return ;
}
for(; i < n ; i++){
while(multiply(p[i],s[top],s[top-]) >= )
top--;
s[++top] = p[i];
}
return top + ;
}
double Triangle_area(POINT a,POINT b,POINT c){
return fabs(multiply(a,b,c)/);
}
double Rotation_Calipers(int len){ //旋转卡壳求凸包最大三角形
double ans = ;
for(int i = ; i < len ; i++){
int j = (i + ) % len;
int k = (j + ) % len;
while(j != i && k != i){
ans = max(ans,Triangle_area(s[i],s[j],s[k]));
while(Triangle_area(s[i],s[j],s[(k+)%len]) > Triangle_area(s[i],s[j],s[k]))
k = (k + ) % len;
j = (j + ) % len;
}
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("ou.txt","w",stdout);
int n;
while(~scanf("%d",&n)){
if(n == -) break;
for(int i = ; i < n ; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
int len = Graham_scan(p,s,n);
double ans = Rotation_Calipers(len);
printf("%.2lf\n",ans);
}
return ;
}

最新文章

  1. s:if 判断
  2. 大前端学习笔记整理【一】CSS盒模型与基于盒模型的6种元素居中方案
  3. Github学习之路-小试牛刀,练习Git 的基本操作
  4. ASP.NET MVC学习系列(二)-WebAPI请求(转)
  5. 第九章 CSS-DOM
  6. [SQL]SUTFF内置函数的用法 (删除指定长度的字符并在指定的起始点插入另一组字符)
  7. 数学之美 zt
  8. jquery 获取元素的 实际宽度和高度
  9. C - 下沙小面的(2)
  10. 一切app源于生活 用于生活 一个利于生活的app——利生活
  11. ArcGIS API for JavaScript 入门教程[4] 代码的骨架
  12. Oracle数据库备份及还原
  13. [Swift]LeetCode220. 存在重复元素 III | Contains Duplicate III
  14. Dapp混合模型开发--Dice2win的解读
  15. 火币网API文档——REST API 签名认证
  16. aspectj ----- 简介
  17. 利用Django构建web应用及其部署
  18. Best Cow Line---poj3617(贪心)
  19. windows的类似shell 命令操作
  20. BZOJ 1014 [JSOI2008]火星人prefix (Splay + Hash + 二分)

热门文章

  1. 添加本地 yum源
  2. 四、YOLO-V1原理与实现(you only look once)
  3. luogu-1908 逆序对 离散化+树状数组
  4. Unity Shader (五)Surface Shader示例
  5. 【转】 java RSA加密解密实现
  6. python里面 __future__的作用 &amp; 下划线的作用 &amp; 3.0实现不换行
  7. Pretty UI Design For Android -- 滑动背景、透明列表
  8. STL 源代码剖析 算法 stl_algo.h -- search
  9. C++中友元类使用场合
  10. Tomcat部署项目修改浏览器上猫咪头像