結果

問題 No.325 マンハッタン距離2
ユーザー NekosyndromeNekosyndrome
提出日時 2015-12-18 01:09:53
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,392 bytes
コンパイル時間 3,436 ms
コンパイル使用メモリ 155,740 KB
実行使用メモリ 4,352 KB
最終ジャッジ日時 2023-10-14 13:37:19
合計ジャッジ時間 2,752 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 2 ms
4,352 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 1 ms
4,352 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 1 ms
4,348 KB
testcase_07 AC 1 ms
4,352 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,352 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 2 ms
4,352 KB
testcase_14 AC 1 ms
4,352 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 1 ms
4,352 KB
testcase_17 AC 1 ms
4,352 KB
testcase_18 AC 1 ms
4,352 KB
testcase_19 AC 1 ms
4,352 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 2 ms
4,348 KB
testcase_22 AC 2 ms
4,348 KB
testcase_23 AC 1 ms
4,348 KB
testcase_24 AC 1 ms
4,348 KB
testcase_25 AC 2 ms
4,352 KB
testcase_26 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 __float128 D;
typedef long double LD;
D eps=1e-13;
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((LD)x.y, (LD)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; }
LL round(D x)
{
	LL sei = (LL)x;
	D aa = x - sei;
	D bb = sei+1 - x;

	if(aa<=bb) return sei;
	return sei+1;
}
int sgn(D x)
{
	return (x>eps) - (x<-eps);
}
int sgn(LL x)
{
	return (x>0) - (x<0);
}
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) );
		
		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) );

		if(d==0)
		{
			if(x1<=0 && 0<=x2 && y1<=0 && 0<=y2)
			{
				puts("1");
			}
			else
			{
				puts("0");
			}
			continue;
		}

		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;
}
0