首页 > 代码库 > XDU_1064:Desolator in RA2
XDU_1064:Desolator in RA2
问题转化为,单个面积*2-交面积。下面求交面积。把直角坐标系中全部转90°,每个方块的坐标都做相应变化,这样会发现新的坐标系中空出了一部分方块,找规律发现,若求交矩形包含的方框数,其中恰好一半是前面空出来的方块。所以实际交面积=转换后坐标系上交矩形面积/2。
题面链接: http://acm.xidian.edu.cn/problem.php?id=1064
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 5 struct point 6 { 7 LL x,y; 8 }; 9 10 LL S(LL r) 11 { 12 LL d=2*r+1; 13 return (d*d+1)/2; 14 } 15 16 LL xxx(point A,point B) 17 { 18 LL x=abs(A.x+A.y-B.x-B.y)+1; 19 LL y=abs(A.x-A.y-B.x+B.y)+1; 20 return (x*y+1)/2; 21 } 22 23 24 int main() 25 { 26 LL x1,x2,y1,y2,r,x,y; 27 while(cin>>x1>>y1>>x2>>y2>>r) 28 { 29 point p; 30 p.x=x=abs(x1-x2); 31 p.y=y=abs(y1-y2); 32 if(p.x+p.y>2*r) 33 { 34 cout<<2*S(r)<<‘\n‘; 35 continue; 36 } 37 point A,B; 38 if(abs(x)+abs(y-r)<=r) 39 { 40 A.x=0,A.y=r; 41 B.x=x,B.y=y-r; 42 } 43 else 44 { 45 A.x=r,A.y=0; 46 B.x=x-r,B.y=y; 47 } 48 cout<<2*S(r)-xxx(A,B)<<‘\n‘; 49 } 50 }
XDU_1064:Desolator in RA2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。