結果

問題 No.960 マンハッタン距離3
ユーザー kmjp
提出日時 2019-12-23 01:35:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,901 bytes
コンパイル時間 1,653 ms
コンパイル使用メモリ 171,856 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-14 22:52:48
合計ジャッジ時間 24,874 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 3
other AC * 78 WA * 19 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,(Y[0]+Y[1])/2,W-1,(Y[0]+Y[1])/2);
	}
	else if(Y0==Y1) {
		add_line(V,(X[0]+X[1])/2,0,(X[0]+X[1])/2,H-1);
	}
	else if(abs(X[0]-X[1])<abs(Y[0]-Y[1])) {
		int y0,y1;
		if(Y[0]<Y[1]) {
			y0=(Y[0]+Y[1]+(X[1]-X[0]))/2;
			y1=(Y[0]+Y[1]-(X[1]-X[0]))/2;
		}
		else {
			y0=(Y[0]+Y[1]-(X[1]-X[0]))/2;
			y1=(Y[0]+Y[1]+(X[1]-X[0]))/2;
		}
		add_line(V,0,y0,X[0]-1,y0);
		add_line(V,X[0],y0,X[1],y1);
		add_line(V,X[1]+1,y1,W-1,y1);
	}
	else if(abs(X[0]-X[1])>abs(Y[0]-Y[1])) {
		int x0,x1;
		if(X[0]<X[1]) {
			x0=(X[0]+X[1]+(Y[1]-Y[0]))/2;
			x1=(X[0]+X[1]-(Y[1]-Y[0]))/2;
		}
		else {
			x0=(X[0]+X[1]-(Y[1]-Y[0]))/2;
			x1=(X[0]+X[1]+(Y[1]-Y[0]))/2;
		}
		add_line(V,x0,0,x0,Y[0]-1);
		add_line(V,x0,Y[0],x1,Y[1]);
		add_line(V,x1,Y[1]+1,x1,H-1);
	}
	else {
		if(Y[0]<Y[1]) {
			add_area(V,0,Y[1],X[0],H-1);
			add_area(V,X[1],0,W-1,Y[0]);
			add_line(V,X[0]+1,Y[1]-1,X[1]-1,Y[0]+1);
		}
		else {
			add_area(V,0,0,X[0],Y[1]);
			add_area(V,X[1],Y[0],W-1,H-1);
			add_line(V,X[0]+1,Y[1]+1,X[1]-1,Y[0]-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