On the way to the park Gym - 101147I 几何

​​http://codeforces.com/gym/101147/problem/I​​

I. On the way to the park

time limit per test

memory limit per test

input

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?

Input

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 ≤ 10⁵), the number of wireless networks, (0 < M ≤ 10⁹), the radius of the coverage area of Asem's device.

Then N lines follow, each describes a wireless network and contains three integers ( - 10⁹ ≤ x_i ≤ 10⁹), the X coordinate of the center of the i'th network coverage area,( - 10⁹ ≤ y ≤ 10⁹), the Y coordinate of the center of the i'th network coverage area, (1 ≤ r_i ≤ 10⁹), 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.

Output

For each test case print one integer. The maximum number that could be displayed on the screen.

Example

Input

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

Output

3
1

Note

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-10;
bool flag;
double calcLeft(LL x, LL y, LL r) {
    double t = m - r;
    double res = t * t - y * y;
    if (res < 0) {
        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 = 1; 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() == 0) {
        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 0;
}

View Code