bzoj5099 [POI2018]Pionek 双指针
2024-10-07 08:48:09
题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=5099
题解
这道题做法似乎挺单一的。
(一开始想了个假做法
向量和的长度等于所有向量在其方向上投影的长度和。
为了最大化长度的话,要能够保证所有向量在长度和的方向上投影都是正的。
所以可以枚举与向量和垂直的向量作为一个端点,那么另一个端点的方向应该和它的差距不超过 \(180\)。
所以可以双指针枚举一下左右端点,一边移动一边统计就没有问题了。
时间复杂度 \(O(n\log n)\) (就是排序的复杂度)。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 200000 * 2 + 7;
const double PI = 3.1415926535897932384626433;
int n;
struct Node {
ll x, y;
double a;
inline Node(const ll &x = 0, const ll &y = 0) : x(x), y(y) {}
inline ll glen() { return x * x + y * y; }
inline Node operator + (const Node &b) { return Node(x + b.x, y + b.y); }
inline Node operator - (const Node &b) { return Node(x - b.x, y - b.y); }
inline bool operator < (const Node &b) const { return a < b.a; }
} a[N], s[N];
inline void work() {
int p = 1;
ll ans = 0;
for (int i = 1; i <= n; ++i) {
smax(p, i);
smax(ans, (s[p] - s[i - 1]).glen());
while (p < i + n - 1 && a[p + 1].a <= a[i].a + PI) ++p, smax(ans, (s[p] - s[i - 1]).glen());
}
printf("%lld\n", ans);
}
inline void init() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i].x), read(a[i].y), a[i].a = atan2(a[i].y, a[i].x);
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) a[i + n] = a[i], a[i + n].a = a[i].a + PI * 2;
for (int i = 1; i <= (n << 1); ++i) s[i] = s[i - 1] + a[i];
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}
最新文章
- sqldeveloper
- WIN7 IIS7 安装方法
- UIImageWriteToSavedPhotosAlbum
- WinStore开发知识导航集锦
- C语言泛型编程--抽象数据类型
- MONO Jexus部署最佳体验
- Typescript的面向对象
- RabbitMQ安装与搭建
- 机器人学 —— 轨迹规划(Introduction)
- 【转】shell 教程——03 Shell脚本语言与编译型语言的差异
- [配置文件] C#修改App.config,Web.config文件帮助类,ConfigHelper (转载)
- 让动态创建的ActiveX控件响应Windows消息
- 使用cordova开发app
- 【webpack】-- 模块热替换
- Java面向对象-方法的值传递和引用传递
- 获取验证码倒计时60s
- 运维常用mysql语句
- php中0,空,null和false之间区别
- 第6月第6天 opengles 三角形
- 查看docker容器日志
热门文章
- Python 字符串与列表去重
- python读取文件时遇到非法字符的处理 UnicodeDecodeError: &#39;gbk&#39; codec can&#39;t decode bytes in position
- docker英语
- SAAS方法论
- python-接口开发flask模块(二)全局host配置
- kafka 通信报文格式
- scala 使用case 关键字定义类不需要创建对象直接调用
- Linux进程状态——top,ps中看到进程状态D,S,Z的含义
- 手写一个IOC容器
- Linux /dev/shm