# 洛谷 P2997 [USACO10NOV]旗帜Banner

2021年09月15日 阅读数：2

## 题目描述

Bessie is returning from a long trip abroad, and Farmer John wants to erect a nice 'Welcome Home' banner in her pasture for her arrival. The banner will hang between two poles on a wire whose length is in the range L1..L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500).ui

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 integerspa

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.code

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.ip

Consider the example pasture below, with W = 2 and H = 1:ci

* * * * * * 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:get

``(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.

## 输入输出格式

* Line 1: Four space-separated integers: W, H, L1, and L2

* Line 1: A single integer denoting the number of possible banners

## 输入输出样例

```2 1 2 3
```

`2 思路：枚举三角形的长和宽来自大神`
```这样的题目必定要规划好枚举的方向，咱们尝试先枚举两维。

L2≤x2+y2≤R2，gcd(x,y)=1```
```#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,l,r;
long long ans;
int gcd(int x,int y){ return x==0?y:gcd(y%x,x); }
int main(){
scanf("%d%d%d%d",&n,&m,&l,&r);
if(l==1){ ans+=1ll*(n+1)*m+1ll*(m+1)*n; }
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
double Len=sqrt(i*i+j*j);
if(Len<l||Len>r||gcd(i,j)!=1)    continue;
ans+=2LL*(n-i+1)*(m-j+1);
}
cout<<ans;
}```