結果

問題 No.2769 Number of Rhombi
ユーザー tails
提出日時 2024-06-04 00:35:23
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 54 ms / 5,000 ms
コード長 3,030 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 29,284 KB
実行使用メモリ 13,312 KB
最終ジャッジ日時 2024-12-23 10:44:25
合計ジャッジ時間 2,960 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:8:59: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
    8 | #define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);})
      |                                                           ^~~~~
main.c:156:9: note: in expansion of macro ‘wt1’
  156 |         wt1(z);
      |         ^~~
main.c:157:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
  157 |         _exit(0);
      |         ^~~~~
main.c:157:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define rd_signed() ({long _s=*rp=='-'&&++rp,_v=rd();_s?-_v:_v;})
#define wt(v) ({unsigned _z=v;do*--wp=_z%10+48;while(_z/=10);})
#define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);})
#define rep(v,e) for(typeof(e) v=0;v<e;++v)
typedef unsigned long ulong;
int n;
struct{int x,y;}xy[1000];
struct cd{ulong c,d;}cd1[500000],cd2[500000],cdbuf[500000];
int cd1n,cd2n;
void sort_aux1(struct cd*a,struct cd*b,int n){
    int c[65536];
    for(int i=0;i<65536;++i){
        c[i]=0;
    }
    for(int i=0;i<n;++i){
        ++c[a[i].d&65535];
    }
    int t=0;
    for(int i=0;i<65536;++i){
        int u=c[i];
        c[i]=t;
        t+=u;
    }
    for(int i=0;i<n;++i){
        int k=c[a[i].d&65535]++;
        b[k].c=a[i].c;
        b[k].d=a[i].d>>16|a[i].d<<48;
    }
}
void sort_aux2(struct cd*a,struct cd*b,int n){
    int c[65536];
    for(int i=0;i<65536;++i){
        c[i]=0;
    }
    for(int i=0;i<n;++i){
        ++c[a[i].c&65535];
    }
    int t=0;
    for(int i=0;i<65536;++i){
        int u=c[i];
        c[i]=t;
        t+=u;
    }
    for(int i=0;i<n;++i){
        int k=c[a[i].c&65535]++;
        b[k].c=a[i].c>>16|a[i].c<<48;
        b[k].d=a[i].d;
    }
}
void sort(struct cd*a,int n){
    struct cd*b=cdbuf;
    sort_aux1(a,b,n);
    sort_aux1(b,a,n);
    sort_aux1(a,b,n);
    sort_aux1(b,a,n);
    sort_aux2(a,b,n);
    sort_aux2(b,a,n);
    sort_aux2(a,b,n);
    sort_aux2(b,a,n);
}
static inline
int gcd(int a,int b){
    int x=__builtin_ctz(a);
    int y=__builtin_ctz(b);
    a>>=x;
    b>>=y;
    for(int c;c=a-b;){
        c>>=__builtin_ctz(c);
        if(c<0){
            b=-c;
        }else{
            a=c;
        }
    }
    return a<<(x<=y?x:y);
}
int main(){
    rd_init();
    n=rd();
    rep(i,n){
        xy[i].x=rd_signed();
        xy[i].y=rd_signed();
        rep(j,i){
            int cx=xy[i].x+xy[j].x;
            int cy=xy[i].y+xy[j].y;
            ulong c=(ulong)(unsigned)cy<<32|(ulong)(unsigned)cx;
            int dx=xy[i].x-xy[j].x;
            int dy=xy[i].y-xy[j].y;
            if(dy==0){
                cd1[cd1n].c=c;
                cd1[cd1n].d=1;
                ++cd1n;
            }else if(dx==0){
                cd2[cd2n].c=c;
                cd2[cd2n].d=1;
                ++cd2n;
            }else{
                if(dy<0){
                    dx=-dx;
                    dy=-dy;
                }
                if(dx>=0){
                    unsigned g=gcd(dx,dy);
                    dx/=g;
                    dy/=g;
                    cd1[cd1n].c=c;
                    cd1[cd1n].d=(ulong)(unsigned)dy<<32|(ulong)(unsigned)dx;
                    ++cd1n;
                }else{
                    dx=-dx;
                    unsigned g=gcd(dx,dy);
                    dx/=g;
                    dy/=g;
                    cd2[cd2n].c=c;
                    cd2[cd2n].d=(ulong)(unsigned)dx<<32|(ulong)(unsigned)dy;
                    ++cd2n;
                }
            }
        }
    }
    sort(cd1,cd1n);
    sort(cd2,cd2n);
    --cd1n;
    --cd2n;
    int z=0;
    while(cd1n>=0&&cd2n>=0){
        if(cd1[cd1n].c<cd2[cd2n].c||cd1[cd1n].c==cd2[cd2n].c&&cd1[cd1n].d<cd2[cd2n].d){
            --cd2n;
        }else
        if(cd1[cd1n].c>cd2[cd2n].c||cd1[cd1n].c==cd2[cd2n].c&&cd1[cd1n].d>cd2[cd2n].d){
            --cd1n;
        }else{
            int a1=cd1n;
            while(cd1n>=0&&cd1[cd1n].c==cd1[a1].c&&cd1[cd1n].d==cd1[a1].d){
                --cd1n;
            }
            int a2=cd2n;
            while(cd2n>=0&&cd2[cd2n].c==cd2[a2].c&&cd2[cd2n].d==cd2[a2].d){
                --cd2n;
            }
            z+=(a1-cd1n)*(a2-cd2n);
        }
    }
    wt1(z);
    _exit(0);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0