洛谷 P2997 [USACO10NOV]旗帜Banner

2021年09月15日 阅读数:2
这篇文章主要向大家介绍洛谷 P2997 [USACO10NOV]旗帜Banner,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目背景

题目大意(by:曹彦臣):ios

平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其余点,且长度在[l,h]范围内。ide

征求翻译。若是你能提供翻译或者题意简述,请直接发讨论,感谢你的贡献。post

题目描述

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

 

输入输出样例

输入样例#1: 复制
2 1 2 3 
输出样例#1: 复制
2 
思路:枚举三角形的长和宽
来自大神
这样的题目必定要规划好枚举的方向,咱们尝试先枚举两维。

由于这个图的左右是对称的,咱们能够只考虑全部斜率>0的线段:根据这条,咱们能够分出当线段与水平/竖直方向平行的状况来。显然,只有所有长度为1的线段知足要求,此时若是1在[L,R][L,R]内,则须要加上这些状况。

咱们还能够算出一个格点图内与当前枚举的线段相同的线段个数:将这条线段视做与横竖直线构成了一个Rt△Rt△,那么问题能够转化为求在格点图中与该Rt△Rt△相同的个数,这个只须要O(1)O(1)便可完成(对于直角边分别为x,y的Rt△Rt△,在纵方向上有(n-x+1)种可能性,在横方向上有(m-y+1)种可能性,根据乘法原理获得个数),因此重点是在枚举不一样的Rt△Rt△。

经过分析两个条件,咱们能够知道一个符合要求的Rt△Rt△(设直角边分别为x,y)必须知足:
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;
}

 

细雨斜风做晓寒。淡烟疏柳媚晴滩。入淮清洛渐漫漫。 雪沫乳花浮午盏,蓼茸蒿笋试春盘。人间有味是清欢。