Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1607-91f88308
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #33 D問題 - Knights (この記事を編集する[管理者用])

Source

Codeforces Beta Round #33 D問題
Problem description
Beta Round #33の自分の参加記録

問題概要

2次元平面上の1000個以下の点と1000個以下の互いに交わらない円周が与えられる.
クエリが100000個与えられて,ある点とある点を線で結ぶために,跨ないといけない最小の円周の数を求める問題.

解法

TopCoder SRM443 DIV1 EASYと同じような問題.
片方の点が円に含まれていて,もう片方が含まれていないような円の数が答え.
愚直にやっても間に合うが,以下のコードはビット演算を使って高速化している.

C言語のスパゲッティなコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
int bit[817637];

int bit_count(int n){
  int res=0;
  while(n){
    res += bit[n%(1<<16)];
    n >>= 16;
  }
  return res;
}

int is_in(ll dx,ll dy,ll r){
  if(r*r < dx*dx + dy*dy) return 1;
  return 0;
}

int main(){
  int i,j,k,l,m,n,q,M;
  int x[1200], y[1200];
  int r[1200], cx[1200], cy[1200];
  int in[1200][40];
  int res;

  rep(i,1<<16){
    k=0; m=i;
    while(m) m&=(m-1), k++;
    bit[i]=k;
  }

  scanf("%d%d%d",&n,&m,&q);
  M = m/30 + 2;
  rep(i,n) rep(j,M) in[i][j]=0;

  rep(i,n) scanf("%d%d",x+i,y+i);
  rep(i,m) scanf("%d%d%d",r+i,cx+i,cy+i);

  rep(i,n) rep(j,m) if(is_in(x[i]-cx[j],y[i]-cy[j],r[j])){
    in[i][j/30] |= (1<<(j%30));
  }

  while(q--){
    scanf("%d%d",&i,&j); i--; j--;
    res=0;
    rep(k,M) res += bit_count(in[i][k]^in[j][k]);
    printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1607-91f88308
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。