Problem 1040 - Banner
小戴的建议也不错，不过先把这题发上来。
Problem 1040 - Banner
Time Limit: 1000MS Memory Limit: 65536KB Difficulty:
Total Submit: 4 Accepted: 4 Special Judge: No
Description
Bessie is returning from a long trip abroad, and Farmer John wantsto erect a nice "Welcome Home" banner in her pasture for her arrival.The banner will hang between two poles on a wire whose length isin the range L1..L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500).
The pasture's size is W x H (1 <= W <= 1,000; 1 <= H <= 1,000), and Farmer John has installed a post at every point with integer coordinates. Of these (W + 1) * (H + 1) points, Farmer John must pick just two that will hold either end of the wire from which he will hang the banner.
FJ wants no interference with his banner as it hangs and requires that no post be directly under the tight wire he stretches between the two chosen posts.
Farmer John needs your help to figure out how many possible ways he can hang the banner. He knows the number is large and that a 32-bit integer might not be sufficient to compute the answer.
Consider the example pasture below, with W = 2 and H = 1:
* * *
* * *
The banner size is in the range 2..3. This pasture contains (2+1)* (1+1) = 6 points and has (6 take 2) = (6*5)/(2*1) = 15 different potential pairs of points between which the banner-holding wire might stretch:
(0,0)-(0,1) (0,0)-(2,1) (0,1)-(2,1) (1,1)-(2,0)
(0,0)-(1,0) (0,1)-(1,0) (1,0)-(1,1) (1,1)-(2,1)
(0,0)-(1,1) (0,1)-(1,1) (1,0)-(2,0) (2,0)-(2,1)
(0,0)-(2,0) (0,1)-(2,0) (1,0)-(2,1)
Of these pairs, only four have a length in the range 2..3:
Len Len
(0,0)-(2,0) 2.00 (0,1)-(2,0) 2.24
(0,0)-(2,1) 2.24 (0,1)-(2,1) 2.00
Of these four, the pairs (0,0)-(2,0) and (0,1)-(2,1) both have a post directly on the line between the endpoints, and thus are unsuitable.
So, just two pairs of points out of 15 are acceptable candidates for hanging the banner wire.
Input
Line 1: Four space-separated integers: W, H, L1, and L2
Output
Line 1: A single integer denoting the number of possible banners
Sample Input
2 1 2 3
Sample Output
2
Hint
Source
USACO NOV10 SILVER
分析
好久不见奶牛贝斯和农夫约翰了，呵呵这可是USACO里很出名的故事人物。
在 W x H 的农场里找两个点，使得它们的距离介于L1与L2之间，而且它们的连线上不能有其它点。问这样的点对有多少。
如果把这两个点当做一个矩形的对角线，那问题就转化成在农场里可以划出多少个矩形。
而要求这个矩形的对角线上没有其它点，既是要求矩形的两边是互质的。
程序代码：
#include<stdio.h>
long long cal(int W, int H, int L1, int L2)
{
long long c;
int i, j, di, d, t, t1, t2;
c = L1 == 1 ? W * H * 2 + W + H : 0;
L1 *= L1;
L2 *= L2;
for(di = i = 1; i <= W; di += (++i << 1) - 1)
for(d = di + (j = 1); j <= H && d <= L2; d += (++j << 1) - 1)
{
if(d < L1) continue;
for(t1 = i, t2 = j; t = t1 % t2; t1 = t2, t2 = t);
if(t2 == 1) c += (W - i + 1) * (H - j + 1) << 1;
}
return c;
}
int main()
{
int W, H, L1, L2;
scanf("%d%d%d%d", &W, &H, &L1, &L2);
printf("%lld\n", cal(W, H, L1, L2));
return 0;
}
[
本帖最后由 beyondyf 于 2012-12-22 20:45 编辑 ]
2012-12-09 16:13
