結果

問題 No.960 マンハッタン距離3
ユーザー kmjp
提出日時 2019-12-23 01:48:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,836 bytes
コンパイル時間 1,657 ms
コンパイル使用メモリ 171,944 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 23:18:39
合計ジャッジ時間 26,598 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 3
other AC * 84 WA * 13 RE * 119
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

ll H,W;
int N;
ll X[101010],Y[101010];


struct area{
	int type;
	int X[2],Y[2];
} ;

void add_line(vector<area>& A,int X0,int Y0,int X1,int Y1) {
	if(X0>X1) return;
	if(X0==X1 && Y0>Y1) return;
	
	area a;
	
	if(Y0==Y1) a.type=0;
	else if(X0==X1) a.type=1;
	else if(Y0<Y1) a.type=2;
	else a.type=3;
	
	a.X[0]=X0;
	a.X[1]=X1;
	a.Y[0]=Y0;
	a.Y[1]=Y1;
	A.push_back(a);
}

void add_area(vector<area>& A,int X0,int Y0,int X1,int Y1) {
	if(X0>X1) return;
	if(Y0>Y1) return;
	
	area a;
	a.type=4;
	
	a.X[0]=X0;
	a.X[1]=X1;
	a.Y[0]=Y0;
	a.Y[1]=Y1;
	A.push_back(a);
	
}

ll get_area(area a) {
	ll ret=0;
	if(a.type==4) {
		return (ll)(a.X[1]-a.X[0]+1)*(a.Y[1]-a.Y[0]+1);
	}
	else {
		return max(abs(a.X[0]-a.X[1]),abs(a.Y[0]-a.Y[1])+1);
	}
}

vector<area> hoge(int X0,int Y0,int X1,int Y1) {
	vector<area> V;
	if(X0>X1) swap(X0,X1),swap(Y0,Y1);
	if(X0==X1) {
		add_line(V,0,(Y0+Y1)/2,W-1,(Y0+Y1)/2);
	}
	else if(Y0==Y1) {
		add_line(V,(X0+X1)/2,0,(X0+X1)/2,H-1);
	}
	else if(abs(X0-X1)<abs(Y0-Y1)) {
		int y0,y1;
		if(Y0<Y1) {
			y0=(Y0+Y1+(X1-X0))/2;
			y1=(Y0+Y1-(X1-X0))/2;
		}
		else {
			y0=(Y0+Y1-(X1-X0))/2;
			y1=(Y0+Y1+(X1-X0))/2;
		}
		add_line(V,0,y0,X0-1,y0);
		add_line(V,X0,y0,X1,y1);
		add_line(V,X1+1,y1,W-1,y1);
	}
	else if(abs(X0-X1)>abs(Y0-Y1)) {
		int x0,x1;
		if(Y0<Y1) {
			x0=(X0+X1+(Y1-Y0))/2;
			x1=(X0+X1-(Y1-Y0))/2;
			add_line(V,x0,0,x0,Y0-1);
			add_line(V,x1,Y1,x0,Y0);
			add_line(V,x1,Y1+1,x1,H-1);
		}
		else {
			x0=(X0+X1-(Y1-Y0))/2;
			x1=(X0+X1+(Y1-Y0))/2;
			add_line(V,x0,Y0+1,x0,H-1);
			add_line(V,x1,Y1,x0,Y0);
			add_line(V,x1,0,x1,Y1-1);
		}
	}
	else {
		if(Y0<Y1) {
			add_area(V,0,Y1,X0,H-1);
			add_area(V,X1,0,W-1,Y0);
			add_line(V,X0+1,Y1-1,X1-1,Y0+1);
		}
		else {
			add_area(V,0,0,X0,Y1);
			add_area(V,X1,Y0,W-1,H-1);
			add_line(V,X0+1,Y1+1,X1-1,Y0-1);
		}
	}
	return V;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H;
	cin>>N;
	int C[2]={};
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		X[i]--;
		Y[i]--;
		C[(X[i]+Y[i])%2]++;
	}
	
	if(C[0]>0 && C[0]<N) return _P("0\n");
	
	if(N==2) {
		auto V=hoge(X[0],Y[0],X[1],Y[1]);
		ll ret=0;
		FORR(a,V) ret+=get_area(a);
		cout<<ret<<endl;
	}
	else {
		assert(0);
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}
0