Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

April 2011 Challenge 6問目 - Rectangles Counting (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 6問目
Problem Statement
April 2011 Challengeの参加記録

問題概要

2次元平面上の格子点がN点 (10^5以下) 与えられる.
その格子点から4つ選んで,革変がx軸y軸に平行な長方形は何パターン作ることができるかを求める問題.
同じx座標に3点以上ないことを仮定して良い.
座標の値の絶対値は10^9以下.

解法

同じx座標に2つの点があるものを取り出してきて,そのy座標の組が一致するものが何個あるか数える.
ハッシュなりsetなりに突っ込んで数えれば良い.

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
#define ull unsigned ll

#define ULL_HASH_SIZE 200000
ull ull_hash_n[ULL_HASH_SIZE]; int ull_hash_d[ULL_HASH_SIZE];

void ullHashClear(void){ memset(ull_hash_d,0,ULL_HASH_SIZE*sizeof(int)); }
int ullHashFunction(ull a){ return (a*1007)%ULL_HASH_SIZE; }

int ullHashGet(ull a){
  int i=ullHashFunction(a);
  for(;;){
    if(ull_hash_n[i]==a && ull_hash_d[i]) break;
    if(!ull_hash_d[i]) break;
    i++; if(i==ULL_HASH_SIZE) i=0;
  }
  if(ull_hash_n[i]!=a) return 0; return ull_hash_d[i];
}

void ullHashSet(ull a,int n){
  int i=ullHashFunction(a);
  for(;;){
    if(ull_hash_n[i]==a && ull_hash_d[i]) break;
    if(!ull_hash_d[i]) break;
    i++; if(i==ULL_HASH_SIZE) i=0;
  }
  ull_hash_n[i]=a; ull_hash_d[i]=n;
}

int ullHashIncrease(ull a){
  int i=ullHashFunction(a);
  for(;;){
    if(ull_hash_n[i]==a && ull_hash_d[i]) break;
    if(!ull_hash_d[i]) break;
    i++; if(i==ULL_HASH_SIZE) i=0;
  }
  ull_hash_n[i]=a; return ++ull_hash_d[i];
}

void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

int main(){
  int i,j,k,l,m,n;
  int x[120000], y[120000];
  ull hs, h1, h2;
  ll res;

  for(;;){
    scanf("%d",&n); if(!n)break;
    rep(i,n) scanf("%d%d",x+i,y+i);
    rep(i,n) y[i] += 1000000010;
    intIntSort(x,y,n);
    ullHashClear();
    res = 0;

    REP(i,1,n) if(x[i-1]==x[i]){
      h1 = y[i-1];
      h2 = y[i];
      if(h1 > h2) hs = h1*2200002020ll + h2 + 192;
      else        hs = h2*2200002020ll + h1 + 192;
      res += ullHashIncrease(hs) - 1;
    }
    printf("%lld\n",res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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