思路：
這道題目的解法非常牛逼。剛一看題就知道做不出來了，所以就在這個博客
http://hi.baidu.com/findthegateopen/
找到了一份解題報告。下面的內(nèi)容都是基于原作者的代碼參考出來的。感謝原作者的代碼！
樸素的做法是O(N^3)的復(fù)雜度。usaco官方的算法是O(N^2)的復(fù)雜度。原作者的代碼跑了不到100ms，應(yīng)該說是相當(dāng)不錯了！
首先，要把所有牛放到坐標(biāo)系上來表示。目的，就是求出包含最多點的直角三角形。
直角三角形的兩條直角邊上都必須有點，也就是一組牛中的具有最小height的點和具有最小width的點。
直角三角形的邊長也是固定的，cw = C/B，ch = C/A。這個還好說，從那個限制條件可以推出來的。初中都學(xué)過，呵呵。
Step1：求出經(jīng)過一個點的所有可能存在的三角形。
其實也就是在該點下方的灰色區(qū)域中選擇點來確定一個三角形。
Step2：求出經(jīng)過一個點的所有可能存在的三角形中，最多包含的點數(shù)。
解法相當(dāng)精妙。
求一個三角形內(nèi)的點數(shù)，可以分解為一個矩形內(nèi)的點數(shù)減去一個梯形內(nèi)的點數(shù)。
用這個方法，求出最上面那個三角形的點數(shù)之后?？梢岳^續(xù)遞推得到下面其他三角形的點數(shù)。
也就是加上一個矩形，再減去一個梯形。
如果點按照高度排序以后，那么后面矩形里的點一定是后出現(xiàn)的。這樣就可以做到隨時增加矩形。
但是減去梯形這個操作，就難理解一點，把點按照A*H + B*W來排序，就能保證后面梯形里的點一定是后出現(xiàn)的。
可見，A*H + B*W 值的大小決定了他們的位置分布。完全可以保證這個順序。
這種數(shù)形結(jié)合的方法實在是相當(dāng)精妙！
那我們就可以首先求出第一個三角形的點數(shù)，然后接下來的三角形就根據(jù)減去梯形，和增加矩形的操作，來做小的調(diào)整就可以了。
在代碼里面的表現(xiàn)形式就是維護(hù)兩個指針，不斷向后移，中間剔除橫坐標(biāo)不在范圍之內(nèi)的點。
這個操作的復(fù)雜度是O(N)。
對所有點執(zhí)行一次，故算法的復(fù)雜度是O(N^2)。
代碼：
/**//*
* 本代碼參考自 http://hi.baidu.com/findthegateopen/
* 中的代碼，感謝原作者的代碼！
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1024
struct node 
{
int w, h, k;
};
struct node in[MAX_N], *sort_h[MAX_N], *sort_k[MAX_N];
int A, B, C, N, ch, cw, ans, box, slash, cnt;
int cmp_h(const void *a, const void *b)
{
return (*(struct node **)b)->h - (*(struct node **)a)->h;
}
int cmp_k(const void *a, const void *b)
{
return (*(struct node **)b)->k - (*(struct node **)a)->k;
}
__inline void update(int h, int w)
{
int k;
for ( ; box < N && sort_h[box]->h >= h; box++)
if (sort_h[box]->w >= w && sort_h[box]->w <= w + cw)
cnt++;
k = A * h + B * w + C;
for ( ; slash < N && sort_k[slash]->k > k; slash++)
if (sort_k[slash]->w >= w && sort_k[slash]->w <= w + cw)
cnt--;
if (cnt > ans)
ans = cnt;
}
__inline void calc(int i)
{
int h, w;
box = 0;
slash = 0;
cnt = 0;
h = sort_h[i]->h;
w = sort_h[i]->w;
for ( ; i < N && sort_h[i]->h >= h - ch; i++)
if (sort_h[i]->w >= w && sort_h[i]->w <= w + cw)
update(sort_h[i]->h, w);
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d%d", &N, &A, &B, &C);
cw = C/B;
ch = C/A;
for (i = 0; i < N; i++) {
scanf("%d%d", &in[i].h, &in[i].w);
in[i].k = A * in[i].h + B * in[i].w;
sort_h[i] = &in[i];
sort_k[i] = &in[i];
}
qsort(sort_h, N, sizeof(sort_h[0]), cmp_h);
qsort(sort_k, N, sizeof(sort_k[0]), cmp_k);
for (i = 0; i < N; i++)
calc(i);
printf("%d\n", ans);
return 0;
}