原题链接：http://codeforces.com/gym/101147/problem/F
题意：n*n的棋盘，给m个主教的坐标及其私有距离p，以及常数C，求位于同一对角线上满足条件：dist(i, j) >= p[i]^2 + p[j]^2 + C
的主教集合的元素个数最大值。
解题思路：
上述条件可以等价为：
d(j) - d(i) +1 >= p[i]^2 + p[j]^2 + C // d(i) 为第i个主教相对于该对角线顶点的距离
d(j) - p[j]^2 - C + 1>= d(i) + p[i]^2
设 f(i) = d(i) + p[i] ^2, g(i) = d(i) - p[i]^2 - C + 1
下面考虑一条对角线，设 c[x] 为长度为x 的最后一个主教编号，例如c[len] = i 代表长度为len的防线最后一个主教编号为i。
(特别的，c[0] = 0, f(0) = -INF )
首先将该对角线上的主教按 d(i) 排序， len 为当前最大长度+1，依次查询每一个主教并同时更新最大长度, 伪代码如下：
对当前查询的主教u
j = lower_bound(c, c+len，u，cmp) - c
if j =len && g(u) >= f(c[j-1])
c[len++] = u
if j != len && g(u) >= f(c[j-1])
c[j] = u
注意： 数据范围为 LL
代码如下：
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = +;
typedef long long LL;
#define INF 999999999999999999LL
vector<int> D1[*maxn];
vector<int> D2[*maxn]; int c[maxn];
int row[maxn], col[maxn], p[maxn];
int n, m, C;
//计算对角线编号
int dig_id1(int x, int y) {return x-y+n;}
int dig_id2(int x, int y) {return x+y;} int d1(int i) {return min(row[i], col[i]);}
int d2(int i) {return min(n-row[i]+, col[i]);} LL f1(int i) {return !i ? -INF : d1(i) + LL(p[i])*p[i];}
LL f2(int i) {return !i ? -INF : d2(i) + LL(p[i])*p[i];} LL g1(int i) {return d1(i) - LL(p[i])*p[i] - C + ;}
LL g2(int i) {return d2(i) - LL(p[i])*p[i] - C + ;} bool cmpd1(int i, int j) {return d1(i) < d1(j);}
bool cmpd2(int i, int j) {return d2(i) < d2(j);}
bool cmp1(const int& a,const int& b) {return f1(a) < f1(b);}
bool cmp2(const int& a,const int& b) {return f2(a) < f2(b);}
LL (*f[])(int) ={
f1,
f2
};
LL (*g[])(int) = {
g1,
g2
};
bool (*cmp[])(const int& ,const int& ) = {
cmp1,
cmp2
}; int cal(vector<int> &D,int flag) {
if(!D.size()) return ;
if(flag == ) sort(D.begin(), D.end(), cmpd1);
else sort(D.begin(), D.end(), cmpd2);
for(int i = ; i <= D.size(); i++) c[i] = ;
int len = ;
int j;
for(int i = ; i < D.size(); i++){
int u = D[i];
j = lower_bound(c, c+len, u, cmp[flag]) - c;
if(j == len && g[flag](u) >= f[flag](c[j-])) {
c[len++] = u;
}
if(j != len && g[flag](u) >= f[flag](c[j-])) {
c[j] = u;
}
}
return len - ;
}
#define fin stdin
int main() {
// FILE * fin;
// fin = fopen("bishops.in", "r");
int T;
fscanf(fin, "%d", &T);
while(T--) {
fscanf(fin, "%d%d%d", &n, &m, &C);
for(int i = ; i <= *n; i++) D1[i].clear();
for(int i = ; i <= *n; i++) D2[i].clear();
for(int i = ; i <= m; i++) {
fscanf(fin, "%d%d%d", &row[i], &col[i], &p[i]);
int id1 = dig_id1(row[i], col[i]);
int id2 = dig_id2(row[i], col[i]);
D1[id1].push_back(i);
D2[id2].push_back(i);
}
int ans = ;
for(int i = ; i <= *n; i++) {
ans = max(ans, cal(D1[i], ));
ans = max(ans, cal(D2[i], ));
}
printf("%d\n", ans);
}
return ;
}