比赛 |
EYOI与SBOI开学欢乐赛5th |
评测结果 |
AWWWWWWWWWWWWAAAWWWW |
题目名称 |
卫星覆盖 |
最终得分 |
20 |
用户昵称 |
康尚诚 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2022-09-16 21:18:25 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
struct node
{
int right;int left;//左右(x轴)
int up;int down;//上下(y轴)
int front;int bhind;//前后(z轴)
int v;//体积
}squre[10010];
node epty;//用来判断结构体是否全部为0
int cnt=0;
node cover(node a,node b)//返回a与b的重叠部分
{
if(a.v>b.v)
{
swap(a,b);
}
node ans;
if(a.up>=b.down&&a.up<=b.up)//如果a的上端在b内
{
ans.up=a.up;//重叠部分的上端必定为a的上端
ans.down=max(a.down,b.down);//下端为a与b的下端中靠上的那个
}
else if(a.down<=b.up&&a.down>=b.down)//同理
{
ans.down=a.down;
ans.up=min(a.up,b.up);
}
else//a与b在y轴上不重叠,则重叠部分为空
{
node ls;
return ls;//返回一个空结构体
}
///////////////////判断左右(x轴)是否重叠,原理同上
if(a.right>=b.left&&a.right<=b.right)
{
ans.right=a.right;
ans.left=max(a.left,b.left);
}
else if(a.left<=b.right&&a.left>=b.left)
{
ans.left=a.left;
ans.right=min(a.right,b.right);
}
else
{
node ls;
return ls;
}
///////////////////判断前后(z轴)是否重叠,原理同上
if(a.front>=b.bhind&&a.front<=b.front)
{
ans.front=a.front;
ans.bhind=max(a.bhind,b.bhind);
}
else if(a.bhind<=b.front&&a.bhind>=b.bhind)
{
ans.bhind=a.bhind;
ans.front=min(a.front,b.front);
}
else
{
node ls;
return ls;
}
ans.v=(ans.up-ans.down)*(ans.right-ans.left)*(ans.front-ans.bhind);
return ans;
}
int main()
{
freopen("satellitecover.in","r",stdin);
freopen("satellitecover.out","w",stdout);
int n,x,y,z,r,ans=0;
cin>>n;cnt=n;
for(int i=1;i<=n;i++)
{
// cin>>x>>y>>r;
cin>>x>>y>>z>>r;
squre[i].left=x-r;squre[i].right=x+r;
squre[i].down=y-r;squre[i].up=y+r;
squre[i].bhind=z-r;squre[i].front=z+r;
int s=pow(r*2,3);
squre[i].v=s;
ans+=s;
}
if(n==1)
{
cout<<ans;
return 0;
}
if(n==2)
{
cout<<ans-cover(squre[1],squre[2]).v;
return 0;
}
if(n==3)
{
node a=cover(squre[1],squre[2]),b=cover(squre[2],squre[3]),c=cover(squre[1],squre[3]);
// cout<<a.v<<" "<<b.v<<" "<<c.v<<" "<<cover(cover(a,b),c).v;
cout<<ans-a.v-b.v-c.v+cover(cover(a,b),c).v;
}
else
{
cout<<ans;
}
}