結果

問題 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);
}
0