显示代码纯文本
#define maxn 200010ul
#include <stdio.h>
#include <assert.h>
#include <algorithm>
typedef long long ll;
inline void read(int &x){
x=0;int c=getchar();
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
return;
}
struct point{int x,y;};
struct node{int cnt,len;};
struct polygon{point l,r;};
struct segment{int l,r,h,type;};
struct Trangle{int x,r;};
struct pdd{
int x,y,r;
void scan(){read(x),read(y),read(r);}
};
namespace compute{
#define cson l,r,rt
#define lson l,mid,t
#define rson mid+1,r,t|1
node tree[maxn<<2];
segment pt[maxn];
int m,cnt,posl,posr,upv,pos[maxn];
bool cmp_segment(const segment &a,const segment &b){
return a.h<b.h;
}
void upd(int l,int r,int rt){
if(tree[rt].cnt) tree[rt].len=pos[r+1]-pos[l]; else
if(l==r) tree[rt].len=0; else
tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
return;
}
void update(int l,int r,int rt){
if(posl<=l&&posr>=r){tree[rt].cnt+=upv,upd(cson);return;}
int mid=(l+r)>>1,t=rt<<1;
if(posl<=mid) update(lson);
if(posr>mid) update(rson);
upd(cson);return;
}
void build(int l,int r,int rt){
tree[rt]=(node){0,0};
if(l==r) return;
int mid=(l+r)>>1,t=rt<<1;
build(lson),build(rson);
return;
}
int binary_search(int v){
int l=1,r=m,mid;
while(l<=r){
mid=(l+r)>>1;
if(pos[mid]==v) return mid;
else if(pos[mid]>v) r=mid-1;
else l=mid+1;
}
return 0;
}
int get_ray(const polygon &x,int p){
if(p==0) return x.l.x;
else return x.r.x;
}
segment convert_to_segment(const polygon &x,int p){
if(p==0) return (segment){x.l.x,x.r.x,x.l.y,-1};
else return (segment){x.l.x,x.r.x,x.r.y,1};
}
void print(const polygon &x){
printf("ltop : %d %d \n",x.l.x,x.l.y);
printf("rtop : %d %d \n",x.r.x,x.r.y);
puts("");return;
}
void arrange(polygon *st,polygon *ed){
for(;st!=ed;++st){
if((*st).l.x>(*st).r.x) std::swap((*st).l.x,(*st).r.x);
if((*st).l.y<(*st).r.y) std::swap((*st).l.y,(*st).r.y);
(*st).r.y--,(*st).r.x++;
}
return;
}
ll rectangle_cross_area(int n,polygon *py){
ll ans=0;m=cnt=0;
for(int i=1;i<=n;i++){
pt[++cnt]=convert_to_segment(py[i],0),pos[cnt]=get_ray(py[i],0);
pt[++cnt]=convert_to_segment(py[i],1),pos[cnt]=get_ray(py[i],1);
}
std::sort(pt+1,pt+cnt+1,cmp_segment);
std::sort(pos+1,pos+cnt+1);
pos[0]=-0x7fffffff;
for(int i=1;i<=cnt;i++) if(pos[i]!=pos[i-1]) pos[++m]=pos[i];
build(1,m,1);
for(int i=1;i<=cnt;i++){
posl=binary_search(pt[i].l),posr=binary_search(pt[i].r)-1;
if(posl<=posr) upv=pt[i].type,update(1,m,1);
ans+=1ll*tree[1].len*(pt[i+1].h-pt[i].h);
}
return ans;
}
}
namespace compute2{
using std::abs;
Trangle tmp[maxn];
void upd(ll &x,ll y){
if(y>x) x=y;return;
}
bool cmp_Trangle(const Trangle &x,const Trangle &y){
return x.x-x.r<y.x-y.r;
}
int dist(const pdd &p,int x,int y){
return abs(p.x-x)+abs(p.y-y);
}
bool inRange(const pdd &p,int x,int y){
return dist(p,x,y)<=p.r;
}
ll area(ll x){
return (1ll+x)*x>>1ll;
}
ll outA(int N,int M,const pdd &x){
return area(x.r-dist(x, 0,M+1)+1);
}
ll outC(int N,int M,const pdd &x){
return area(x.r-dist(x,N+1,M+1)+1);
}
ll outF(int N,int M,const pdd &x){
return area(x.r-dist(x, 0, 0)+1);
}
ll outH(int N,int M,const pdd &x){
return area(x.r-dist(x,N+1, 0)+1);
}
ll exceed_ACFH(int N,int M,int n,pdd *data){
ll maxA=0,maxC=0,maxF=0,maxH=0;
for(int i=1;i<=n;i++){
if(inRange(data[i],0 ,M+1)) upd(maxA,outA(N,M,data[i]));
if(inRange(data[i],N+1,M+1)) upd(maxC,outC(N,M,data[i]));
if(inRange(data[i],0 , 0)) upd(maxF,outF(N,M,data[i]));
if(inRange(data[i],N+1, 0)) upd(maxH,outH(N,M,data[i]));
}
return maxA+maxC+maxF+maxH;
}
ll calRi(int r){
return 1ll*((r<<1)+2)*(r+1)>>1ll;
}
ll calRi2(int r){
return 1ll*((r<<1)+2)*r>>1ll;
}
ll trangleArea(const Trangle &x){
return calRi(x.r);
}
bool trangleIn(const Trangle &x,const Trangle &y){
return x.x-x.r<=y.x-y.r&&x.x+x.r>=y.x+y.r;
}
bool notCross(const Trangle &x,const Trangle &y){
return x.x+x.r<y.x-y.r;
}
ll sameArea(const Trangle &x,const Trangle &y){
int l=y.x-y.r,r=x.x+x.r;
if((r-l+1)&1) return calRi((r-l)>>1);
return calRi2((r-l+1)>>1);
}
ll dp_trangle(int n,Trangle *pt){
if(!n) return 0;
int T=1;
std::sort(pt+1,pt+n+1,cmp_Trangle);
ll ans=trangleArea(pt[1]);
for(int i=2;i<=n;i++){
if(trangleIn(pt[T],pt[i])) continue;
else if(notCross(pt[T],pt[i])) ans+=trangleArea(pt[i]),T=i;
else ans+=trangleArea(pt[i])-sameArea(pt[T],pt[i]),T=i;
}
return ans;
}
ll exceed_Line(int N,int M,int n,pdd *data){
int tot;
ll ans=0;
//Part I - ABC
tot=0;
for(int i=1;i<=n;i++){
if(inRange(data[i],data[i].x,M+1))
tmp[++tot]=(Trangle){data[i].x,data[i].r-dist(data[i],data[i].x,M+1)};
}
ans+=dp_trangle(tot,tmp);
//Part II - CEH
tot=0;
for(int i=1;i<=n;i++){
if(inRange(data[i],N+1,data[i].y))
tmp[++tot]=(Trangle){data[i].y,data[i].r-dist(data[i],N+1,data[i].y)};
}
ans+=dp_trangle(tot,tmp);
//Part III - FGH
tot=0;
for(int i=1;i<=n;i++){
if(inRange(data[i],data[i].x,0))
tmp[++tot]=(Trangle){data[i].x,data[i].r-dist(data[i],data[i].x,0)};
}
ans+=dp_trangle(tot,tmp);
//Part IV - ADF
tot=0;
for(int i=1;i<=n;i++){
if(inRange(data[i],0,data[i].y))
tmp[++tot]=(Trangle){data[i].y,data[i].r-dist(data[i],0,data[i].y)};
}
ans+=dp_trangle(tot,tmp);
return ans;
}
}
pdd data[maxn];
int N,M,n,tot;
polygon sd[maxn];
point cp1(int x,int y){
// assert(!((x+y)&1));
return (point){(x+y)>>1,(y-x)>>1};
}
point cp2(int x,int y){
// assert((x+y)&1);
return cp1(x-1,y);
}
ll part_Unlimited(){
ll ans=0;
//on diagonal
tot=0;
for(int i=1,rb,rc;i<=n;i++){
rb=data[i].r>>1,rc=(data[i].r-1)>>1;
if((data[i].x+data[i].y)&1^1) sd[++tot]=(polygon){cp1(data[i].x-(rb<<1),data[i].y),cp1(data[i].x+(rb<<1),data[i].y)};
else if(data[i].r>1) sd[++tot]=(polygon){cp1(data[i].x-(rc<<1)-1,data[i].y),cp1(data[i].x+(rc<<1)+1,data[i].y)};
}
compute::arrange(sd+1,sd+tot+1);
ans+=compute::rectangle_cross_area(tot,sd);
//not on diaonal
tot=0;
for(int i=1,rb,rc;i<=n;i++){
rb=data[i].r>>1,rc=(data[i].r-1)>>1;
if((data[i].x+data[i].y)&1) sd[++tot]=(polygon){cp2(data[i].x-(rb<<1),data[i].y),cp2(data[i].x+(rb<<1),data[i].y)};
else if(data[i].r>0) sd[++tot]=(polygon){cp2(data[i].x-(rc<<1)-1,data[i].y),cp2(data[i].x+(rc<<1)+1,data[i].y)};
}
compute::arrange(sd+1,sd+tot+1);
ans+=compute::rectangle_cross_area(tot,sd);
return ans;
}
ll part_Exceed(){
ll ans=0;
ans-=compute2::exceed_ACFH(N,M,n,data);
ans+=compute2::exceed_Line(N,M,n,data);
return ans;
}
int main(){
freopen("soldier.in","r",stdin);
freopen("soldier.out","w",stdout);
read(N),read(M),read(n);
for(int i=1;i<=n;i++) data[i].scan();
printf("%lld\n",part_Unlimited()-part_Exceed());
return 0;
}
stdafx.h