@[Maxmilite](/user/274993)
by liaiyang @ 2024-03-26 10:43:50
建议出加强版题目
by PLYnotAK @ 2024-03-26 10:46:00
@[realskc](/user/35672)
by tder @ 2024-03-26 10:46:39
@[PLYnotAK](/user/816227) 加强版继续发扬人类智慧。
by hellolin @ 2024-03-26 10:47:40
建议将两者结合,造一组大圆边界内外套一堆小圆的数据,hack 掉内外接圆人类智慧旋转。如:
```cpp
17
0 0 25
-27 0 1
27 0 1
0 27 1
0 -27 1
-23 0 1
23 0 1
0 23 1
0 -23 1
19 19 1
-19 19 1
19 -19 1
-19 -19 1
-16 -16 1
16 16 1
16 -16 1
-16 16 1
```
答案
```
625
```
by liaiyang @ 2024-03-26 11:06:26
orz
by jijidawang @ 2024-03-26 11:22:31
@[liaiyang](/user/783170)
本来就不是正解,hack错解干嘛
```
const int N=2e5+5;
const db s=sqrt(2)/2;
const db eps=1e-6;
struct Line{
db x,l,r;
}line[N<<2];
bool cmp(Line a,Line b){
return a.x<b.x;
}
int n,cnt=0;
db Y[N<<2];
int sum[N<<4];
db len[N<<4];
void add(db x1,db x2,db y1,db y2){
line[++cnt]={x1,y1,y2},Y[cnt]=y1;
line[++cnt]={x2,y1,y2},Y[cnt]=y2;
}
void push_up(int root,int l,int r){
if(sum[root])len[root]=Y[r+1]-Y[l];
else len[root]=len[ls(root)]+len[rs(root)];
}
void push_down(int root,int l,int r){
int mid=(l+r)/2;
sum[ls(root)]^=sum[root],sum[rs(root)]^=sum[root];
if(sum[root]){
len[ls(root)]=(Y[mid+1]-Y[l])-len[ls(root)];
len[rs(root)]=(Y[r+1]-Y[mid+1])-len[rs(root)];
}
sum[root]=0;
}
void modify(int root,int l,int r,db s,db t){
if(s<=Y[l]+eps&&Y[r+1]<=t+eps){sum[root]^=1,len[root]=(Y[r+1]-Y[l])-len[root];return;}
push_down(root,l,r);
int mid=(l+r)/2;
if(s<Y[mid+1]-eps)modify(ls(root),l,mid,s,t);
if(t>Y[mid+1]+eps)modify(rs(root),mid+1,r,s,t);
push_up(root,l,r);
}
signed main(){
std::cin.tie(0)->sync_with_stdio(0);
std::cin>>n;
FOR(i,1,n){
db x,y,r;
std::cin>>x>>y>>r;
add(x-r*s,x+r*s,y-r,y+r);
add(x-r,x-r*s,y-r*s,y+r*s);
add(x+r*s,x+r,y-r*s,y+r*s);
}
std::sort(line+1,line+1+cnt,cmp);
std::sort(Y+1,Y+1+cnt);
int tot=(std::unique(Y+1,Y+1+cnt)-Y-1);
db ans=0;
FOR(i,1,cnt-1){
modify(1,1,tot-1,line[i].l,line[i].r);
ans+=len[1]*(line[i+1].x-line[i].x);
}
std::cout<<(int)(ans*(2*s+0.5)/7);
return 0;
}
```
by PLYnotAK @ 2024-03-26 11:26:40
@[PLYnotAK](/user/816227) 不hack错解难道hack正解吗/yiw
by MurataHimeko @ 2024-03-26 12:20:53
@[liaiyang](/user/783170) Hack 数据已经添加,感谢您的贡献
by Maxmilite @ 2024-04-04 23:14:38