Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM319 DIV1 HARD - Manhattan (この記事を編集する[管理者用])

Source

TopCoder SRM319 DIV1 HARD (1000pt)
Problem Statement

問題概要

2次元平面上の250000個以下の点が与えられるので,マンハッタン距離で最も離れている点の組を見つける問題.
複数あるなら辞書順で最小のものを求める.

解法

x[i]-y[i]の値でソートした時の最小値と最大値の組,もしくは
x[i]+y[i]の値でソートした時の最小値と最大値の組,が最も離れている組.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
ll x[333333], y[333333];
pair<ll, int> p[333333];

class Manhattan {
public:
vector <int> furthestPair(int n, int a, int b, int m) {
  int i;
  vector <int> res(2,0), tmp(2,0);
  ll opt = -1;

  rep(i,n){
    if(i==0) x[i]=0;
    else x[i] = (a*y[i-1] + b)%m;
    y[i] = (a*x[i] + b)%m;
  }

  rep(i,n) p[i].first = x[i]-y[i], p[i].second = i;
  sort(p,p+n);
  tmp[0]=p[0].second;
  for(i=n-1;i;i--) if(p[i].first!=p[i-1].first) break;
  tmp[1]=p[i].second;
  sort(tmp.begin(),tmp.end());
  
  if(p[n-1].first - p[0].first == opt && tmp < res) opt = -1;
  if(p[n-1].first - p[0].first > opt) opt = p[n-1].first - p[0].first, res = tmp;

  rep(i,n) p[i].first = x[i]+y[i], p[i].second = i;
  sort(p,p+n);
  tmp[0]=p[0].second;
  for(i=n-1;i;i--) if(p[i].first!=p[i-1].first) break;
  tmp[1]=p[i].second;
  sort(tmp.begin(),tmp.end());
  
  if(p[n-1].first - p[0].first == opt && tmp < res) opt = -1;
  if(p[n-1].first - p[0].first > opt) opt = p[n-1].first - p[0].first, res = tmp;

  if(res[0]==res[1]) res[0]=0, res[1]=1;

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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