O(n2logn) 做法,WA on #5 #10,80pts。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll c1, c2, c3;
struct Pear {
ll a, b;
bool operator <(const Pear &W)const {
return c1 * a + c2 * b < c1 * W.a + c2 * W.b;
}
}p[2010], pp[2010];
bool cmpA(const Pear &A, const Pear &B) { return A.a < B.a; }
bool cmpB(const Pear &A, const Pear &B) { return A.b > B.b; }
bool check(ll ai, ll a0, ll bi, ll b0) {
return c1 * (ai - a0) + c2 * (bi - b0) <= c3;
}
int main() {
scanf("%d%lld%lld%lld", &n, &c1, &c2, &c3);
for (int i = 1; i <= n; i++) {
ll j, k;
scanf("%lld%lld", &j, &k);
p[i] = {j, k};
}
sort(p + 1, p + n + 1, cmpA);
ll ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) pp[j] = p[j];
sort(pp + i + 1, pp + n + 1, cmpB);
priority_queue<Pear, vector<Pear>, less<Pear> > q;
for (int j = i + 1; j <= n; j++) {
ll t = min(pp[j].b, p[i].b);
if (!check(pp[j].a, p[i].a, pp[j].b, t)) continue;
q.push({pp[j].a, pp[j].b});
while(q.size() && !check(q.top().a, p[i].a, q.top().b, t)) q.pop();
ll cnt = q.size() + 1;
ans = max(ans, cnt);
}
}
printf("%lld\n", ans);
return 0;
}