首页 > 代码库 > LightOj1366 - Pair of Touching Circles(求矩形内圆的对数)
LightOj1366 - Pair of Touching Circles(求矩形内圆的对数)
题目链接:http://lightoj.com/volume_showproblem.php?problem=1366
题意:一个H*W的矩形,现在要放入两个外切的圆,问能放多少对这样的圆,其中圆心和半径都是整数;
枚举相对的圆心坐标,根据圆心的距离,再枚举一个圆的半径;
#include<stdio.h>#include<iostream>#include<string.h>#include<algorithm>#include<cmath>#include<vector>#include<queue>#include<set>using namespace std;#define met(a, b) memset(a, b, sizeof(a))#define maxn 10005#define maxm 20005#define INF 0x3f3f3f3ftypedef long long LL;int main(){ int T, H, W, t = 1; scanf("%d", &T); while(T--) { LL ans = 0; scanf("%d %d", &H, &W); for(int i=0; i<=W/2; i++)///把一个圆的圆心看成(0,0)时枚举另一个圆的圆心相对坐标(i,j); { for(int j=0; j<=H/2; j++) { if(i==0 && j==0) continue; int d = sqrt(i*i + j*j);///圆心之间的距离; if(d*d != i*i + j*j) continue; for(int r=1; r<d; r++)///枚举其中一个圆的半径; { int x1 = min(-r, i-(d-r)), x2 = max(r, i+(d-r)); int y1 = min(-r, j-(d-r)), y2 = max(r, j+(d-r));///手动画图就明白了; int x = x2 - x1, y = y2 - y1; if(x > W || y > H) continue; LL ret = (LL)(H-y+1)*(W-x+1); if(i*j) ret *= 2;///*2原因是当两个圆的圆心不是水平或垂直方向的时候可以斜着放的是两种情况(斜上)(斜下),我这里的相对位置是(斜上); ans += ret; } } } printf("Case %d: %lld\n", t++, ans);///%lld; } return 0;}
LightOj1366 - Pair of Touching Circles(求矩形内圆的对数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。