結果

問題 No.325 マンハッタン距離2
ユーザー Nekosyndrome
提出日時 2015-12-18 01:09:53
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,392 bytes
コンパイル時間 1,533 ms
コンパイル使用メモリ 170,088 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-16 08:19:31
合計ジャッジ時間 2,347 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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