提交时间:2025-05-08 12:32:20
运行 ID: 37751
#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second using namespace std; const int N=4050,V=2e6+10; int n; vector<int> tlen;//triangle int eve[V][3]; vector<int> lex,ley; struct shape{ int x,y,v; }t[N]; int main(){ cin>>n; for(int i=1;i<=n;i++){ int x,y,v;cin>>x>>y>>v; t[i]=(shape){x,y,v}; lex.push_back(x);lex.push_back(x+v); }sort(lex.begin(),lex.end()); long long ans=0; for(int i=1;i<lex.size();i++){ int lx=lex[i-1],rx=lex[i]; if(lx>=rx) continue; int len=rx-lx; ley.clear();tlen.clear(); for(int j=1;j<=n;j++){ int L=t[j].x,R=t[j].x+t[j].v; if(L<=lx&&rx<=R){ int bd=(R-rx)+t[j].y; ley.push_back(t[j].y); ley.push_back((R-rx)+t[j].y); ley.push_back((R-lx)+t[j].y); eve[t[j].y][0]++; eve[(R-rx)+t[j].y][1]++; eve[(R-rx)+t[j].y][2]++; } }sort(ley.begin(),ley.end()); //cout<<lx<<' '<<rx<<' '<<ans<<endl; int cnt=0; for(int j=1;j<ley.size();j++){ int L=ley[j-1],R=ley[j]; if(L>=R) continue; cnt+=eve[ley[j-1]][0]-eve[ley[j-1]][1]; //cout<<ley[j-1]<<' '<<eve[ley[j-1]][2]<<' '; for(int k=1;k<=eve[ley[j-1]][2];k++) tlen.push_back(len); int now=cnt; //cout<<L<<' '<<R<<' '<<cnt<<' '<<tlen.size()<<' '<<ans<<endl; if(tlen.empty()){ if(cnt&1) ans+=2ll*len*(R-L); }else{ if(cnt&1) ans+=1ll*(R-L)*(len*2+(R-L)-tlen.back()*2); for(int k=tlen.size()-1;k>=1;k--){ now++;if(now&1) ans+=2ll*(tlen[k]-tlen[k-1])*(R-L); }now++; if(now&1) ans+=1ll*(R-L)*(tlen[0]*2-(R-L)); } for(auto &ed:tlen) ed-=(R-L); reverse(tlen.begin(),tlen.end()); while(!tlen.empty()){ if(tlen.back()>0) break;tlen.pop_back(); }reverse(tlen.begin(),tlen.end()); } for(auto ed:ley) memset(eve[ed],0,sizeof(eve[ed])); }printf("%.1Lf",ans/(long double)(2.0));//cout<<endl<<ans<<endl; return 0; }