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

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

  

题意:给你n个坐标点 ,求两点之间的最大距离的平方
题解:求出凸包,枚举顶点两两之间的距离
#include
#include
#include
#include
#include
using namespace std;#define eps 1e-8int top , n;//点struct POINT{ double x, y; POINT(){ } POINT(double a, double b){ x = a; y = b; }}p[50005],st[50005];//线段struct Seg{ POINT a, b; Seg() { } Seg(POINT x, POINT y){ a = x; b = y; }};//叉乘double cross(POINT o, POINT a, POINT b){ return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);}//多边形面积,需要有顺序,顺(逆)时针。double area(){ double ans = 0; for(int i = 1; i < top; i ++){ ans += cross(p[0], p[i], p[i + 1]); } return ans;}//找凸包基点排序bool cmp0(POINT a, POINT b){ if(a.y < b.y) return true; else if(a.y == b.y && a.x < b.x) return true; return false;}double dis(POINT a,POINT b){ return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );}//极角排序bool cmp1(POINT a, POINT b){ if(cross(p[0], a, b) > eps) return true; else if(fabs(cross(p[0], a, b)) < eps && dis(p[0], a) - dis(p[0], b) > eps) return true; return false;}//Graham_scan 求凸包.所求为纯净凸包...void Graham_scan(){ sort(p, p + n, cmp0); sort(p + 1, p + n, cmp1); top = 0; p[n] = p[0]; st[top ++] = p[0]; st[top ++] = p[1]; for(int i = 2; i <= n; i ++){ while(top > 2 && (cross(st[top - 1], st[top - 2], p[i]) > eps || fabs(cross(st[top - 1], st[top - 2], p[i])) < eps)) top --; st[top ++] = p[i]; } top --;}double dis2(POINT a , POINT b){ return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);}int main(){ while(~scanf("%d",&n)){ for(int i = 0;i < n;i++) scanf("%lf %lf",&p[i].x,&p[i].y); if(n == 2) {printf("%.lf\n",dis2(p[0],p[1]));continue;} Graham_scan(); double _max = 0; for(int i = 0;i < top;i++) for(int j = i+1;j < top;j++) _max = max(_max,dis2(st[i],st[j])); printf("%.0lf\n",_max); }}

转载地址:http://mcsgi.baihongyu.com/

你可能感兴趣的文章
AngularJS路由之ui-router(一)
查看>>
AngularJS路由之ui-router(二)
查看>>
Uncaught Error: datetimepicker component should be placed within a relative positioned container
查看>>
C#进制转换操作(一)
查看>>
C#进制转换操作(二)
查看>>
C#双规获取指定层数的下标排列
查看>>
C#转固定长度字符串
查看>>
JQuery.validationEngine表单验证插件
查看>>
C#字符串连接和StringBuilder字符串拼接性能测试
查看>>
C# Try/Catch性能测试
查看>>
C# DES解密异常问题
查看>>
AngularJS ocLazyLoad按需加载控制器/js文件的延迟加载(一)
查看>>
AngularJS 动态加载控制器实例-ocLoazLazy(二)
查看>>
AngularJS动画(一)
查看>>
SqlServer消息 6107,级别 14 只能终止用户进程。
查看>>
ng-if和ng-show的区别
查看>>
ng-if指令
查看>>
ng-switch指令
查看>>
SqlServer2008T-Sql收缩数据库日志文件
查看>>
ng-include指令
查看>>