#66659 (C++11) No.325 マンハッタン距離2

• 問題: No.325 マンハッタン距離2
• ユーザー: Nekosyndrome
• 提出日時: 2015-12-18 00:53:59
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 3,245 bytes
• コンパイル時間: 1,500 ms
• コンパイル使用メモリ: 169,276 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-09-16 08:15:39
• 合計ジャッジ時間: 2,263 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	1 ms; 6,940 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	WA	-
testcase_04	AC	1 ms; 6,944 KB
testcase_05	AC	1 ms; 6,944 KB
testcase_06	AC	1 ms; 6,944 KB
testcase_07	WA	-
testcase_08	AC	2 ms; 6,944 KB
testcase_09	AC	1 ms; 6,944 KB
testcase_10	AC	2 ms; 6,940 KB
testcase_11	AC	2 ms; 6,948 KB
testcase_12	AC	2 ms; 6,940 KB
testcase_13	AC	1 ms; 6,940 KB
testcase_14	AC	2 ms; 6,940 KB
testcase_15	AC	1 ms; 6,944 KB
testcase_16	AC	1 ms; 6,944 KB
testcase_17	AC	2 ms; 6,940 KB
testcase_18	AC	1 ms; 6,940 KB
testcase_19	AC	1 ms; 6,940 KB
testcase_20	AC	1 ms; 6,940 KB
testcase_21	AC	1 ms; 6,940 KB
testcase_22	AC	2 ms; 6,940 KB
testcase_23	WA	-
testcase_24	AC	2 ms; 6,940 KB
testcase_25	AC	1 ms; 6,944 KB
testcase_26	AC	1 ms; 6,940 KB

ソースコード

#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define FORD(x,y,z) for(int x=y;x>=z;x--)
#define MSET(x,y) memset(x,y,sizeof(x))
#define FOR(x,y) for(__typeof(y.begin()) x=y.begin();x!=y.end();x++)
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SZ size()
#define M 105
#define y1 My_Y1
void RI(){}
template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d",&head);
    RI(tail...);
}
using namespace std;
typedef long long LL;
typedef long double D;
D eps=1e-8;
struct P
{
	D x,y;
	P(){}
	P(int a,int b){ x=a; y=b; }
	P operator + (P a) { return P(x+a.x, y+a.y); }
	P operator - (P a) { return P(x-a.x, y-a.y); }
	D operator * (P a) { return x*a.y - y*a.x; }
	D operator % (P a) { return x*a.x + y*a.y; }
	P operator * (D a) { return P(x*a, y*a); }
};
D atan2(P x)
{
	return atan2(x.y, x.x);
}
struct Line
{
	P s,e;
	D a;
	Line (){}
	Line (P _a,P b,D c){ s=_a; e=b; a=c; }
};
bool cmpa(Line a,Line b){ return a.a<b.a; }
int sgn(D x)
{
	return (x>eps) - (x<-eps);
}
int nok(Line l,P d)
{
	return sgn( (l.e-l.s) * (d-l.s) ) <= 0;
}
P getjiao(Line aa,Line bb)
{
	P a=aa.s, b=aa.e, c=bb.s, d=bb.e;
	D d1 = (b-a)*(c-d);
	D d2 = (c-a)*(c-d);
	P jd = a+ (b-a)*(d2/d1);
	return jd;
}
Line dq[M];
P jp[M];
int qs,qe;
int mianjiao(Line *a,int n)
{
	sort(a,a+n,cmpa);
	///////////////unique
	int m=1;
	for(int i=1;i<n;i++)
	{
		if(sgn(a[i].a-a[m-1].a))a[m++]=a[i];
		else if(nok(a[i],a[m-1].s))a[m-1]=a[i];
	}
	n=m;
	///////////////
	qs=qe=0;
	dq[qe++]=a[0];
	dq[qe++]=a[1];
	jp[qe-1]=getjiao(dq[qe-1],dq[qe-2]);
	for(int i=2;i<n;i++)
	{
		for(;qe-qs>=2&&nok(a[i],jp[qe-1]);qe--);
		for(;qe-qs>=2&&nok(a[i],jp[qs+1]);qs++);
		D parl =(a[i].e-a[i].s)*(dq[qe-1].e-dq[qe-1].s);
		if(sgn(parl)==0)return 0;
		dq[qe++]=a[i];
		jp[qe-1]=getjiao(dq[qe-1],dq[qe-2]);
	}
	for(;qe-qs>=2&&nok(dq[qs+0],jp[qe-1]);qe--);
	for(;qe-qs>=2&&nok(dq[qe-1],jp[qs+1]);qs++);
	if(qe-qs<=2)return 0;
	jp[qs]=getjiao(dq[qs],dq[qe-1]);
	return 1;
}
Line a[M];int at;
void addl(P s,P e)
{
	a[at++]=Line(s,e,atan2(e-s));
}
int x1,y1,x2,y2,d;

int main()
{
	while(~scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&d))
	{
		at = 0;
		addl( P(d,0), P(0,d) );
		addl( P(0,d), P(-d,0) );
		addl( P(-d,0), P(0,-d) );
		addl( P(0,-d), P(d,0) );
		
		int INF = 200;
		
		addl( P(x2, -1), P(x2,1) );
		addl( P(x1, 1), P(x1,-1) );
		addl( P(-1, y1), P(1, y1) );
		addl( P(1, y2), P(-1, y2) );

	//	addl( P(x2, -INF), P(x2,INF) );
	//	addl( P(x1, INF), P(x1,-INF) );
	//	addl( P(-INF, y1), P(INF, y1) );
	//	addl( P(INF, y2), P(-INF, y2) );

		int x = mianjiao(a, at);
		if(x==0)
		{
			puts("0");
			continue;
		}

		vector<P> vec;
		REP(i,qs+1,qe-1)
		{
			vec.PB( getjiao(dq[i], dq[i-1]) );
		}
		vec.PB( getjiao(dq[qs], dq[qe-1]) );

		LL edge=0, ins=0;
		LL area=0, tmp;
		vec.PB(vec[0]);
		REP(i,1,(int)vec.SZ-1)
		{
			area += (LL)round(vec[i].x) * round(vec[i-1].y) - (LL)round(vec[i].y) * round(vec[i-1].x);
			
			tmp = max(
				abs( (LL)round(vec[i].x)-round(vec[i-1].x) ),
				abs( (LL)round(vec[i].y)-round(vec[i-1].y) )
			);
			edge += tmp;
		}
		area = abs(area);

//		FOR(i,vec) printf("%f %f\n",i->x,i->y);
//		printf("area = %lld\n",area);

		ins = (area-edge+2)/2;
		printf("%lld\n", ins+edge);
		
	}
	return 0;
}