题目大意:n个点,任意几个点组合后得到的点距离原点的最远距离。

题解:极角排序:https://blog.csdn.net/qq_39942341/article/details/79840394

利用极角排序,将这些点看成与原点相作用的向量,然后根据平行四边行法则,两向量之间的角度相差越小,其复合得到的向量的长度越长。

#include<bits/stdc++.h>
using namespace std;
const int N=1E5+;
struct stu{
double a,b;
bool friend operator <(const stu &x,const stu &y){
return atan2(x.b,x.a)<atan2(y.b,y.a);
}
}arr[N];
int nxt[N];
int main(){
int n;
cin>>n;
for(int i=;i<=n;i++) cin>>arr[i].a>>arr[i].b;
for(int i=;i<=n;i++) nxt[i]=i+;
nxt[n]=;
sort(arr+,arr++n);
double ans=;
for(int i=;i<=n;i++){//以每个点为起始点,遍历一圈后回到起始点,同时记录大小
double dx=arr[i].a;
double dy=arr[i].b;
ans=max(ans,arr[i].a*arr[i].a+arr[i].b*arr[i].b); for(int j=nxt[i];j!=i;j=nxt[j]){
dx+=arr[j].a;
dy+=arr[j].b;
ans=max(ans,dx*dx+dy*dy);
}
}
printf("%.15lf\n",sqrt(ans));
return ;
}

最新文章

  1. Idea 实时编译 和 热部署
  2. C#-ASP.NET MVC-架构【1】-自定义错误页
  3. Eclipse svn插件包
  4. 读取xml文件报错:Invalid byte 2 of 2-byte UTF-8 sequence。
  5. dtw算法
  6. Apache Spark技术实战之4 -- 利用Spark将json文件导入Cassandra
  7. Java for LeetCode 035 Search Insert Position
  8. poj3449Geometric Shapes
  9. AspectJ的简单使用
  10. 我的第一个JApplet-绘制笑脸
  11. git操作github
  12. 【转载】HTML和XML的区别
  13. hdu 4472 Count (2012 ACM-ICPC 成都现场赛)
  14. final使用
  15. Knowledge point
  16. CentOS7 Failed to start LSB: Bring up/down解决方法
  17. linux 修改内核参数 如何生效?
  18. 截取字符串中最后一个中文词语(MS SQL)
  19. Thinkphp的S缓存用法!
  20. python中序列化json模块和pickle模块

热门文章

  1. PHP中$$的应用
  2. [暴力+前缀和]2019牛客暑期多校训练营(第六场)Upgrading Technology
  3. HTTP、TCP、IP协议面试题
  4. (数据科学学习手札81)conda+jupyter玩转数据科学环境搭建
  5. 大型Java进阶专题(五) 设计模式之单例模式与原型模式
  6. Python如何用virtualenv搭建虚拟环境
  7. OpenCV-Python 轨迹栏作为调色板 | 九
  8. 带权并查集 HDU - 3047
  9. python中面向对象&amp;装饰器
  10. 数据库(sqlserver 2005)优化排查之路