题意：$W \times H$ 的表格中，有 $n$ 个质点从某方格中心同时开始运动。没有两个质点初始时在同一方格中。所有质点以同样的速度做直线运动，方向为上、下、左、右之一。如果两个或多个质点在同一时刻位于同一位置，则这些质点相撞并消失。求被质点经过的格子数。

这里每个质点用三个参数 $x$，$y$，$d$ 来描述，表示其开始运动的位置是从左往右的 $x$ 列、从上往下的第 $y$ 行的方格的中心。运动的方向由 $d$ 表示，分别为：

• $d = 0$，表示向右；
• $d = 1$，表示向上；
• $d = 2$，表示向左；
• $d = 3$，表示向下。

$1 \le n \le 10^5$，$1 \le w \le 10^9$，$1 \le h \le 10^9$；$1 \le x \le W$，$1 \le y \le H$，$0 \le d \le 3$。

只用求出每个质点的运动路程，然后看作宽为 $1$ 的矩形做扫描线即可。

求运动路程，就只需要求相撞的情况。相撞质点的方向有 $6$ 种可能，如同一行，左边的向右，右边的向左；再如同一条左上—右下对角线，左边的向下，右边的向左；等等。具体的可以看代码。

在每一种可能中，最先相撞的一定是两个相邻的点。一旦遇到两个相撞，就要删去这两个点，考虑新产生的相邻对，于是使用链表。

按照 $6$ 种情形，$4$ 个方向排序，排序后构建链表。然后将所有相撞按时间放入一个堆中，每次取出某个时刻所有的相撞，判断是否存在（可能已经撞过）。如果是存在的相撞，就更新链表和堆。

细节：

1. 排序的时候要先按照方向分开。
2. 可以假设质点每秒运动半个方格边长，这样所有的时间都是整数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,INF=1<<30;
int n,W,H,X[N<<1];ll ans;
struct P{int no,x,y,d,nxt[6],lst[6],t,ex;}a[N];
int fir[]={0,3,0,3,0,1},sec[]={2,1,1,2,3,2},dx[]={1,0,-1,0},dy[]={0,-1,0,1};
bool cmp(P a,P b){return a.no<b.no;}
bool cmp1(P a,P b){
	if((a.d==0||a.d==2)&&(b.d==1||b.d==3))return true;
	if((b.d==0||b.d==2)&&(a.d==1||a.d==3))return false;
	return a.y!=b.y?a.y<b.y:a.x<b.x;
}
bool cmp2(P a,P b){
	if((a.d==1||a.d==3)&&(b.d==0||b.d==2))return true;
	if((b.d==1||b.d==3)&&(a.d==0||a.d==2))return false;
	return a.x!=b.x?a.x<b.x:a.y<b.y;
}
bool cmp3(P a,P b){
	if((a.d==0||a.d==1)&&(b.d==2||b.d==3))return true;
	if((b.d==0||b.d==1)&&(a.d==2||a.d==3))return false;
	return a.x-a.y!=b.x-b.y?a.x-a.y<b.x-b.y:a.x<b.x;
}
bool cmp4(P a,P b){
	if((a.d==0||a.d==3)&&(b.d==1||b.d==2))return true;
	if((b.d==0||b.d==3)&&(a.d==1||a.d==2))return false;
	return a.x+a.y!=b.x+b.y?a.x+a.y<b.x+b.y:a.x<b.x;
}
struct hit{int t,p,q;};
bool operator <(const hit &a,const hit &b){return a.t>b.t;}
priority_queue<hit> Q;
struct ScanLine{
	ll l,r,h;int op;
	bool operator <(const ScanLine &b){
		return h<b.h;
	}
}line[N<<1];
struct SegmentTree{
	int ls[N<<3],rs[N<<3],sum[N<<3];ll len[N<<3];
	#define lc p<<1
	#define rc p<<1|1
	void push_up(int p){
		if(sum[p])len[p]=X[rs[p]+1]-X[ls[p]];
		else len[p]=len[lc]+len[rc];
	}
	void build(int p,int l,int r){
		ls[p]=l;rs[p]=r;len[p]=sum[p]=0;
		if(l==r)return;
		build(lc,l,l+r>>1);
		build(rc,(l+r>>1)+1,r);
	}
	void modify(int p,int L,int R,int c){
		if(X[rs[p]+1]<=L||R<=X[ls[p]])return;
		if(L<=X[ls[p]]&&X[rs[p]+1]<=R){sum[p]+=c;push_up(p);return;}
		modify(lc,L,R,c);modify(rc,L,R,c);
		push_up(p);
	}
}seg;
int main(){
	scanf("%d%d%d",&W,&H,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d);
		a[i].ex=1;a[i].no=i;
		for(int k=0;k<6;k++)a[i].nxt[k]=a[i].lst[k]=-1;
		switch(a[i].d){
			case 0:a[i].t=2*(W-a[i].x);break;
			case 1:a[i].t=2*(a[i].y-1);break;
			case 2:a[i].t=2*(a[i].x-1);break;
			case 3:a[i].t=2*(H-a[i].y);break;
		}
	}
	a[n+1].d=2;a[0].d=0;
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<n;i++){
		if(a[i].d==1||a[i].d==3)break;
		if(a[i].y==a[i+1].y)a[i].nxt[0]=a[i+1].no,a[i+1].lst[0]=a[i].no;
	}
	sort(a+1,a+n+1,cmp2);
	for(int i=1;i<n;i++){
		if(a[i].d==0||a[i].d==2)break;
		if(a[i].x==a[i+1].x)a[i].nxt[1]=a[i+1].no,a[i+1].lst[1]=a[i].no;
	}
	sort(a+1,a+n+1,cmp3);
	for(int i=0,op=2;i<n;i++){
		if((a[i].d==0||a[i].d==1)&&(a[i+1].d==2||a[i+1].d==3)){op=3;continue;}
		if(i!=0&&a[i].x-a[i].y==a[i+1].x-a[i+1].y)
			a[i].nxt[op]=a[i+1].no,a[i+1].lst[op]=a[i].no;
	}
	sort(a+1,a+n+1,cmp4);
	for(int i=0,op=4;i<n;i++){
		if((a[i].d==0||a[i].d==3)&&(a[i+1].d==1||a[i+1].d==2)){op=5;continue;}
		if(i!=0&&a[i].x+a[i].y==a[i+1].x+a[i+1].y)
			a[i].nxt[op]=a[i+1].no,a[i+1].lst[op]=a[i].no;
	}
	sort(a+1,a+n+1,cmp);
	for(int k=0;k<6;k++)
		for(int i=1;i<=n;i++)
			if(a[i].nxt[k]!=-1&&a[i].d==fir[k]&&a[a[i].nxt[k]].d==sec[k])
				Q.push({abs(a[i].x-a[a[i].nxt[k]].x)+abs(a[i].y-a[a[i].nxt[k]].y),i,a[i].nxt[k]});
	while(!Q.empty()){
		int t0=Q.top().t;
		while(!Q.empty()&&Q.top().t==t0){
			hit tmp=Q.top();int i=tmp.p,j=tmp.q;Q.pop();
			if(!a[i].ex&&a[i].t!=t0||!a[j].ex&&a[j].t!=t0)continue;
			if(a[i].ex){
				for(int k=0;k<6;k++){
					int LS=a[i].lst[k],NX=a[i].nxt[k];
					if(LS!=-1)a[LS].nxt[k]=NX;
					if(NX!=-1)a[NX].lst[k]=LS;
					if(LS!=-1&&NX!=-1&&a[LS].d==fir[k]&&a[NX].d==sec[k])
						Q.push({abs(a[LS].x-a[NX].x)+abs(a[LS].y-a[NX].y),LS,NX});
				}
			}
			if(a[j].ex){
				for(int k=0;k<6;k++){
					int LS=a[j].lst[k],NX=a[j].nxt[k];
					if(LS!=-1)a[LS].nxt[k]=NX;
					if(NX!=-1)a[NX].lst[k]=LS;
					if(LS!=-1&&NX!=-1&&a[LS].d==fir[k]&&a[NX].d==sec[k])
						Q.push({abs(a[LS].x-a[NX].x)+abs(a[LS].y-a[NX].y),LS,NX});
				}
			}
			a[i].t=a[j].t=t0;a[i].ex=a[j].ex=0;
		}
	}
	for(int i=1;i<=n;i++){
		int dist=a[i].t,X1,Y1,X2,Y2;
		if(dist%2==0)dist/=2;
		switch(a[i].d){
			case 0:{X1=a[i].x;X2=a[i].x+dist+1;Y1=a[i].y;Y2=a[i].y+1;break;}
			case 1:{X1=a[i].x;X2=a[i].x+1;Y1=a[i].y-dist;Y2=a[i].y+1;break;}
			case 2:{X1=a[i].x-dist;X2=a[i].x+1;Y1=a[i].y;Y2=a[i].y+1;break;}
			case 3:{X1=a[i].x;X2=a[i].x+1;Y1=a[i].y;Y2=a[i].y+dist+1;break;}
		}
		X[2*i-1]=X1;X[2*i]=X2;
		line[2*i-1]={X1,X2,Y1,1};line[2*i]={X1,X2,Y2,-1};
	}
	sort(line+1,line+2*n+1);
	sort(X+1,X+2*n+1);
	int tot=unique(X+1,X+2*n+1)-X-1;
	seg.build(1,1,tot-1);
	for(int i=1;i<2*n;i++){
		seg.modify(1,line[i].l,line[i].r,line[i].op);
		ans+=seg.len[1]*(line[i+1].h-line[i].h);
	}
	printf("%lld\n",ans);
	return 0;
}