博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 2187 Beauty Contest 最远点距
阅读量:5086 次
发布时间:2019-06-13

本文共 1128 字,大约阅读时间需要 3 分钟。

/**求出凸包枚举每个点的矩距离即可  因为凸包上的点可定不多。。学习: 刚开始WA 了一次,,因为用int 存的, 一看discuss 里提供的数据,想起来,,应该是越界了。。后来用longlong 就过了。。**/#include 
#include
#include
using namespace std;struct point { long long x,y; //point (){} point (double x=0,double y=0):x(x),y(y){}};point p[50050],ch[50050];typedef point Vector;Vector operator -(point a,point b){ return Vector (a.x-b.x,a.y-b.y);}long long cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x;}bool cmp(point a,point b){ if(a.x==b.x) return a.y
1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++] = p[i]; } int k = m; for(int i=n-2;i>=0;i--){ while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++] = p[i]; } if(n>1) m--; return m;}int main(){ int n; cin>>n; for(int i=0;i
>p[i].x>>p[i].y; } int m = convexHull(p,n,ch); long long max_len = 0; for(int i=0;i
max_len) max_len = length(ch[j]-ch[i]); } } cout<
<

 

转载于:https://www.cnblogs.com/Bang-cansee/p/3724174.html

你可能感兴趣的文章
android dialog使用自定义布局 设置窗体大小位置
查看>>
ionic2+ 基础
查看>>
互联网模式下我们更加应该“专注”
查看>>
myeclipse集成jdk、tomcat8、maven、svn
查看>>
查询消除重复行
查看>>
Win 10 文件浏览器无法打开
查看>>
HDU 1212 Big Number(C++ 大数取模)(java 大数类运用)
查看>>
-bash: xx: command not found 在有yum源情况下处理
查看>>
[leetcode]Minimum Path Sum
查看>>
内存管理 浅析 内存管理/内存优化技巧
查看>>
hiho1079 线段树区间改动离散化
查看>>
【BZOJ 5222】[Lydsy2017省队十连测]怪题
查看>>
第二次作业
查看>>
【input】 失去焦点时 显示默认值 focus blur ★★★★★
查看>>
Java跟Javac,package与import
查看>>
day-12 python实现简单线性回归和多元线性回归算法
查看>>
Json格式的字符串转换为正常显示的日期格式
查看>>
[转]使用 Razor 进行递归操作
查看>>
[转]Android xxx is not translated in yyy, zzz 的解决方法
查看>>
docker入门
查看>>