HihoCoder 1570 : 小Hi与法阵(简单几何)
2024-09-08 13:28:29
描述
小Hi喜欢大,而小Ho喜欢小。他们所在的城市(视为二维平面)有N座法阵。现在他们各选三座法阵,以三座法阵为顶点组成三角形,并站在所选三角形的重心位置;二人选择的法阵可以有相同的。小Hi选择面积最大的三角形,小Ho选择面积最小的三角形。若有多个面积相同且符合他们要求的三角形,小Hi选择重心横坐标最大的,若重心横坐标相同,则选择重心纵坐标最大的;小Ho选择重心横坐标最小的,若重心横坐标相同,则选择重心纵坐标最小的。
现在两人需要见面,两人均可以在城市里以不超过U的速度向任意方向移动,问他们两个最少经过多长时间可以相会?
例如下图中的例子,共六座法阵,分别为A,B,C,D,E,F,则小Hi位于三角形ABC的重心G上,小Ho位于三角形DEF的重心H上。
注意两人选择的三座法阵必须能组成三角形,不能是共线的。
输入
输入包含多组数据,第一行包含一个数字T,代表数据组数。1<=T<=10
对于每组数据:
第一行为两个整数N、U,分别代表法阵数量和最高移动速度。3<=N<=50,1<=U<=10
接下来N行,每行两个整数Xi和Yi,代表第i所法阵的横纵坐标。-300<=Xi,Yi<=300。
输入保证法阵位置不同。
输出
对于每组数据,输出一行,包含一个数字,代表相会时间,四舍五入保留到小数点后2位。
样例输入
1
3 1
0 10
-10 0
10 5
样例输出
0.00
- 面积可以用向量法或者海伦公式求。
- 判断是否共线,不能直接用斜率相同。解决方案是1,特判y轴相同。2,把除法变为乘法。3,向量法求得的面积为0。
- 用整数避开浮点数的误差。
//向量法
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
const int inf=;
int x[maxn],y[maxn];
int get_S(int i,int j,int k)
{
return abs((x[j]-x[i])*(y[k]-y[i])-(x[k]-x[i])*(y[j]-y[i]));
}
int main()
{
int x1,y1,x2,y2;
int Min,Max;
int i,j,k,n,u,T;
scanf("%d",&T);
while(T--){
Min=inf;Max=-inf;
x1=;y1=inf;x2=;y2=inf;
scanf("%d%d",&n,&u);
for(i=;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for(i=;i<=n;i++)
for(j=i+;j<=n;j++)
for(k=j+;k<=n;k++){
int tmp=get_S(i,j,k);
if(tmp==) continue;
int tx=(x[i]+x[j]+x[k]),ty=(y[i]+y[j]+y[k]);
if(tmp<Min||(tmp==Min&&tx<x1)||(tmp==Min&&tx==x1&&ty<y1)) { Min=tmp;x1=tx;y1=ty;}
if(tmp>Max||(tmp==Max&&tx>x2)||(tmp==Max&&tx==x2&&ty>y2)) { Max=tmp;x2=tx;y2=ty;}
}
double dx=(x1-x2)/3.0,dy=(y1-y2)/3.0;
printf("%.2lf\n",sqrt(dx*dx+dy*dy)/u/2.0);
}return ;
}
最新文章
- css3 翻转和旋转的区别
- Hibernate的批量插入(&;&;JDBC)
- Linux 网络编程详解十二
- 必须正确理解的---ng指令中的compile与link函数解析
- FragmentActivity和Activity的区别
- 超级MINI STLINK V2 官方固件自动升级 ST-Link 【worldsing 笔记】
- access的时间相关的查询
- Android应用开发基础篇(12)-----Socket通信
- IntelliJ IDEA 13 破解安装(JRebel 5.6.3a皴)
- Data Guard组件等相关介绍
- 如何得到AdoConnection.execute(sqlstr)执行的返回结果
- jquery on()动态绑定元素的的点击事件无反应的问题记录
- java 23种设计模式 深入理解
- Python 转路由之uplink
- oracle导出导入指定表
- golang net/http 包
- Jmeter的NON-GUI模式
- Knockout开发中文API系列4–绑定关键字
- Delphi XE5 for Android (一)
- 查看selenium api的方法
热门文章
- [WARNING] Using platform encoding (UTF-8 actually) to copy filtered resources, i.e. build is platform dependent!
- 纯CSS3美化radio和checkbox
- Git学习0基础篇(下)
- iOS UI08_tableView省市区字典数组
- ThinkPHP学习(五)图片验证码
- Something about cache
- kubernetes容器编排之定义环境变量以及通过downwardapi把pod信息作为环境变量传入容器内
- JS 模板引擎 Handlebars.js 中文说明
- 深入Garbage First垃圾收集器(三)G1中的垃圾收集
- OTL中文乱码 OTL UTF8