Description
NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为minV，身高最矮的球员高度为minH，那么这支球队的所有队员都应该满足: A * ( height
– minH ) + B * ( speed – minV ) <= C 其中A和B，C为给定的经验值。这个式子很容易理解，如果一个球队的球员速度和身高差距太大，会造成配合的不协调。 请问作为球队管理层的你，在N名选秀球员中，最多能有多少名符合条件的候选球员。
Input
第一行四个数N、A、B、C 下接N行每行两个数描述一个球员的height和speed
Output
最多候选球员数目。
Sample Input
4 1 2 10
5 1
3 2
2 3
2 1
Sample Output
4
HINT
数据范围： N <= 5000 ,height和speed不大于10000。A、B、C在长整型以内。
思路
这题也真是够神仙的
首先把式子变成这样
$Ax+By-Cle Aminx + Bminy $
然后就重新取一个权值叫做(val=Ax+By-C)
把原数组复制两遍，一个按照x排序，一个按照val排序
然后我们先枚举miny，然后在内层枚举minx，但是同时怎么维护答案？
我们用一个指针扫val加入答案，并用一个指针扫x删除答案
我第一次看到的时候心情就是wtf？
确实很神奇
现在我们考虑加入答案的限制，首先y肯定是要大于等于miny的，但是y应该有一个上界，不然(y-miny)太大导致在满足(valle Aminx+Bminy)的条件下(x< minx)
既然不能让x超界，也就是要满足(minxle x)，那么就一定有
(Byle Bminy + C)
也就是说(minyle yle miny + frac{C}{B})
这样就可以同时扫按照x排序的队列来把x不满足的都删掉了（因为y对于全局的限制都是相等的）
？？？
好像推不过来吧，不过没事，在这道题里面是对的
现在来考虑另一个事情：会不会有没有统计贡献的被删除贡献？
不可能的
被删除贡献的时候需要满足(x<minx)和(minle yle miny+frac{C}{B})
显然是满足(Ax+Byle Aminx+Bminy+C)的
那不就一定会在上面统计贡献吗？
所以就成立了。。。然后其实你也可以根据刚刚这个式子把(Byle Bminy + C)理解为让删除不重不漏的条件
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, A, B, C;
int ans;
struct Point {
int x, y, val;
Point() {}
Point(int x, int y, int val): x(x), y(y), val(val) {}
} p[N], q[N];
bool cmp1(const Point a, const Point b) {
return a.x < b.x;
}
bool cmp2(const Point a, const Point b) {
return a.val < b.val;
}
int main() {
scanf("%d %d %d %d", &n, &A, &B, &C);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d %d", &x, &y);
p[i] = q[i] = Point(x, y, A * x + B * y - C);
}
sort(p + 1, p + n + 1, cmp1);
sort(q + 1, q + n + 1, cmp2);
for (int i = 1; i <= n; i++) {
int tp = 0, tq = 0, cur = 0;
int dn = p[i].y, up = C / B + p[i].y;
for (int j = 1; j <= n; j++) {
int limit = A * p[j].x + B * p[i].y;
while (tp < n && p[tp + 1].x < p[j].x) {
++tp;
cur -= dn <= p[tp].y && p[tp].y <= up;
}
while (tq < n && q[tq + 1].val <= limit) {
++tq;
cur += dn <= q[tq].y && q[tq].y <= up;
}
ans = max(ans, cur);
}
}
printf("%d", ans);
return 0;
}