A - Engines Atcoder 4900
2024-09-04 03:11:11
题目大意: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 ;
}
最新文章
- Idea 实时编译 和 热部署
- C#-ASP.NET MVC-架构【1】-自定义错误页
- Eclipse svn插件包
- 读取xml文件报错:Invalid byte 2 of 2-byte UTF-8 sequence。
- dtw算法
- Apache Spark技术实战之4 -- 利用Spark将json文件导入Cassandra
- Java for LeetCode 035 Search Insert Position
- poj3449Geometric Shapes
- AspectJ的简单使用
- 我的第一个JApplet-绘制笑脸
- git操作github
- 【转载】HTML和XML的区别
- hdu 4472 Count (2012 ACM-ICPC 成都现场赛)
- final使用
- Knowledge point
- CentOS7 Failed to start LSB: Bring up/down解决方法
- linux 修改内核参数 如何生效?
- 截取字符串中最后一个中文词语(MS SQL)
- Thinkphp的S缓存用法!
- python中序列化json模块和pickle模块
热门文章
- PHP中$$的应用
- [暴力+前缀和]2019牛客暑期多校训练营(第六场)Upgrading Technology
- HTTP、TCP、IP协议面试题
- (数据科学学习手札81)conda+jupyter玩转数据科学环境搭建
- 大型Java进阶专题(五) 设计模式之单例模式与原型模式
- Python如何用virtualenv搭建虚拟环境
- OpenCV-Python 轨迹栏作为调色板 | 九
- 带权并查集 HDU - 3047
- python中面向对象&;装饰器
- 数据库(sqlserver 2005)优化排查之路