On the way to the park Gym - 101147I 几何
http://codeforces.com/gym/101147/problem/I
5 seconds
64 megabytes
walk.in
standard output
Engineers around the world share a lot of common characteristics. For example, they're all smart, cool and extremely lazy!
Asem is a computer engineer, so he is very lazy. He doesn't leave the house for weeks. Not even for a shisha with his best friends.
One day his mother insisted that he goes to the park to get some fresh air. Asem is a lazy but a very practical person. He decided to use the time spent on the way to the park to test his new device for detecting wireless networks in the city. The device is as much advanced as it's weird. It detects a network if the coverage area of the network is entirely inside the coverage area of the device. Both the coverage area of the wireless networks and Asem's device are circular shaped.
The path between Asem's house and the park is a straight line and when Asem turn on the device, it display one integer on its screen, the sum of the radiuses of the detected networks.
Given the coordinates of the center of the networks coverage area and their radiuses, what is the maximum number that could be displayed on the screen knowing that Asem can test the device anywhere in the street?
The first line of the input will contain T the number of test cases.
Each test case starts with two integers on a single line (0 < N ≤ 105), the number of wireless networks, (0 < M ≤ 109), the radius of the coverage area of Asem's device.
Then N lines follow, each describes a wireless network and contains three integers ( - 109 ≤ xi ≤ 109), the X coordinate of the center of the i'th network coverage area,( - 109 ≤ y ≤ 109), the Y coordinate of the center of the i'th network coverage area, (1 ≤ ri ≤ 109), the radius of the i'th network coverage area. Where the street is the X-axis here and Asem can test the device anywhere on it.
For each test case print one integer. The maximum number that could be displayed on the screen.
2
3 5
0 0 1
4 0 2
10 0 1
4 3
0 1 1
0 -3 1
10 1 1
0 -4 2
3
1
Large I/O files. Please consider using fast input/output methods.
The figure shows a possible solution for the first sample.
对于每一个圆。可以算出一个区间[L, R]使得半径为m的圆在这个区间里,一定能包含它。
然后就是区间减法问题里。用map存一下就好
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n, m;
const double eps = 1e-;
bool flag;
double calcLeft(LL x, LL y, LL r) {
double t = m - r;
double res = t * t - y * y;
if (res < ) {
flag = false;
return eps;
}
return x - sqrt(res);
}
double calcRight(LL x, LL y, LL r) {
double t = m - r;
double res = t * t - y * y;
// assert(res >= 0);
return x + sqrt(res);
}
map<double, LL>mp;
void work() {
mp.clear();
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) {
int x, y, r;
scanf("%d%d%d", &x, &y, &r);
if (r > m) continue;
flag = true;
double res = calcLeft(x, y, r);
if (flag) {
mp[res] += r;
mp[calcRight(x, y, r) + eps] -= r;
}
}
if (mp.size() == ) {
printf("0\n");
return;
}
map<double, LL> :: iterator it1 = mp.begin();
LL ans = it1->second;
LL pre = it1->second;
it1++;
for (it1; it1 != mp.end(); it1++) {
pre += it1->second;
ans = max(ans, pre);
}
printf("%I64d\n", ans);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
freopen("walk.in", "r", stdin);
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
最新文章
- Mvc model验证总结
- [New Portal]Windows Azure Virtual Machine (11) 在本地使用Hyper-V制作虚拟机模板,并上传至Azure (1)
- FileShare枚举的使用(文件读写锁)
- 很励志的帖子,转来自勉,也反省一下自己写码这几年【奋斗10年,一个.NET程序员从0到拥有5系】
- SQL Agent Job ->;>; 通过sys.sysprocesses的program_name字段来定位对应的Job
- PHP正则表达式 验证电子邮件地址
- [置顶] java 通过classloader加载类再通过classforname实例化
- DNSmasq服务搭建
- markdown笔记实现页内目录跳转
- xilinx Vivado的使用详细介绍(2):创建工程、添加文件、综合、实现、管脚约束、产生比特流文件、烧写程序、硬件验证
- JavaScript 查找图中连接两点的所有路径算法
- Twig---for循环
- JS 中的 __proto__ 、prototype、constructor
- 3D点云数据分析:pointNet++论文分析及阅读笔记
- abstract class和interface有什么区别?
- markdown的试用
- 20145316许心远《网络对抗》第一次实验拓展:shellcode注入+return-to-libc
- 对于单文本或者div的内容怎么在显示东西过多的情况下实现显示隐藏
- 9 tensorflow提示in different while loops的错误该如何解决
- 事后分析报告(Postmortem Report)要求