思路：
這道題目的解法非常牛逼。剛一看題就知道做不出來(lái)了，所以就在這個(gè)博客
http://hi.baidu.com/findthegateopen/
找到了一份解題報(bào)告。下面的內(nèi)容都是基于原作者的代碼參考出來(lái)的。感謝原作者的代碼！
樸素的做法是O(N^3)的復(fù)雜度。usaco官方的算法是O(N^2)的復(fù)雜度。原作者的代碼跑了不到100ms，應(yīng)該說(shuō)是相當(dāng)不錯(cuò)了！
首先，要把所有牛放到坐標(biāo)系上來(lái)表示。目的，就是求出包含最多點(diǎn)的直角三角形。
直角三角形的兩條直角邊上都必須有點(diǎn)，也就是一組牛中的具有最小height的點(diǎn)和具有最小width的點(diǎn)。
直角三角形的邊長(zhǎng)也是固定的，cw = C/B，ch = C/A。這個(gè)還好說(shuō)，從那個(gè)限制條件可以推出來(lái)的。初中都學(xué)過(guò)，呵呵。
Step1：求出經(jīng)過(guò)一個(gè)點(diǎn)的所有可能存在的三角形。
其實(shí)也就是在該點(diǎn)下方的灰色區(qū)域中選擇點(diǎn)來(lái)確定一個(gè)三角形。
Step2：求出經(jīng)過(guò)一個(gè)點(diǎn)的所有可能存在的三角形中，最多包含的點(diǎn)數(shù)。
解法相當(dāng)精妙。
求一個(gè)三角形內(nèi)的點(diǎn)數(shù)，可以分解為一個(gè)矩形內(nèi)的點(diǎn)數(shù)減去一個(gè)梯形內(nèi)的點(diǎn)數(shù)。
用這個(gè)方法，求出最上面那個(gè)三角形的點(diǎn)數(shù)之后?？梢岳^續(xù)遞推得到下面其他三角形的點(diǎn)數(shù)。
也就是加上一個(gè)矩形，再減去一個(gè)梯形。
如果點(diǎn)按照高度排序以后，那么后面矩形里的點(diǎn)一定是后出現(xiàn)的。這樣就可以做到隨時(shí)增加矩形。
但是減去梯形這個(gè)操作，就難理解一點(diǎn)，把點(diǎn)按照A*H + B*W來(lái)排序，就能保證后面梯形里的點(diǎn)一定是后出現(xiàn)的。
可見(jiàn)，A*H + B*W 值的大小決定了他們的位置分布。完全可以保證這個(gè)順序。
這種數(shù)形結(jié)合的方法實(shí)在是相當(dāng)精妙！
那我們就可以首先求出第一個(gè)三角形的點(diǎn)數(shù)，然后接下來(lái)的三角形就根據(jù)減去梯形，和增加矩形的操作，來(lái)做小的調(diào)整就可以了。
在代碼里面的表現(xiàn)形式就是維護(hù)兩個(gè)指針，不斷向后移，中間剔除橫坐標(biāo)不在范圍之內(nèi)的點(diǎn)。
這個(gè)操作的復(fù)雜度是O(N)。
對(duì)所有點(diǎ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;
}