UVA 12373 Pair of Touching Circles

思路：(注意2个圆的半径可以不一样)

有2种情况：

1）水平和竖直放。这种情况很简单，刚开始以为只有这种情况，但是样例5不对，后来知道还有一种情况。

2）斜线也可以放。只要满足勾股数就可以。现在的问题是怎样确定包含2个圆的矩形，可以通过枚举一个圆的半径

来确定。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<set>
 7 #include<vector>
 8 #define ll long long
 9 #define M 1000
10 #define inf 1e10
11 #define mod 1000000007
12 using namespace std;
13 int n,m,cnt;
14 struct node
15 {
16     int x,y,t;
17 }p[M];
18 void init()
19 {
20     cnt=0;
21     for(int i=1;i<500;i++)
22     for(int j=i+1;j<500;j++){
23         int k=i*i+j*j;
24         int t=(int)sqrt(1.0*k);
25         if(t>M) break;
26         if(k==t*t){
27             p[cnt].x=i;
28             p[cnt].t=t;
29             p[cnt++].y=j;
30         }
31     }
32 }
33 ll cal(int a,int b)
34 {
35     int u=a+b;
36     int v=b;
37     ll ans=0,t=0;
38     if(u<=n&&v<=m) t=(n-u+1)*(m-v+1);
39     if(v<=n&&u<=m) t+=(m-u+1)*(n-v+1);
40     if(a!=b) t=2*t;
41     ans+=t;
42     return ans;
43 }
44 int main()
45 {
46     int i,j,k,c,t,ca=0;
47     init();
48     scanf("%d",&t);
49     while(t--){
50         scanf("%d%d",&n,&m);
51         ll ans=0;
52         for(i=2;i<=n||i<=m;i+=2){
53             for(j=i;i+j<=n||i+j<=m;j+=2)
54                 ans+=cal(i,j);
55         }
56         for(i=0;i<cnt;i++)
57         for(j=1;j<p[i].t;j++){
58             int u=max(p[i].x+p[i].t,2*max(j,p[i].t-j));
59             int v=max(p[i].y+p[i].t,2*max(j,p[i].t-j));
60             ll tt=0;
61             if(u<=n&&v<=m) tt=(n-u+1)*(m-v+1);
62             if(u<=m&&v<=n) tt+=(m-u+1)*(n-v+1);
63             ans+=2*tt;
64         }
65         printf("Case %d: %lld
",++ca,ans);
66     }
67     return 0;
68 }

View Code

UVA 12373 Pair of Touching Circles

相关推荐