AtCoder Regular Contest #024 D問題 - バス停

Source

AtCoder Regular Contest #024
問題文

問題概要

$N$ 個のバス停があり,それぞれのバス停 $i$ の座標は $(X_i, Y_i)$ である.
バスは曲がれず,上下左右に移動することしか出ないないので,バス停同士は $x$ 座標,あるいは,$y$ 座標が一致している時に行き来できる.
新しくバス停を設置して,(もともと設置されてたバス停も新しく設置したバス停も両方とも考え)任意のバス停間をバスを乗り継ぐことでマンハッタン距離だけの移動で行き来できるようにしたい.
そのようなバス停の設置方法を $1$ つ求める問題.
ただし,(もともと設置されてたバス停も新しく設置したバス停も両方とも考え)バス停の数は $10000$ を超えてはいけない.
また,同じ点に $2$ つ以上のバス停が存在してはいけない.

解法

分割統治.
まず,直線 $y=k$ の右側にも,左側にも,バス停の数が $N/2$ 個未満となるような $k$ を見つけてくる.
(これは,$y$ 座標でバス停をソートして真ん中のバス停の $y$ 座標を取ってくれば良い)
それぞれのバス停 $(X_i, Y_i)$ に対して,$y=k$ の直線上に,$(X_i, k)$ というバス停を置く.
すると,直線 $y=k$ の左側にある任意のバス停から,右側にある任意のバス停には,マンハッタン距離の移動で行き来ができるようになる.
後は,$y=k$ の左側,および,右側のみを考えて,同じ方法でバス停を設置していく.
そうすると,新しく設置したバス停同士も,マンハッタン距離で行き来できることはすぐに分かる.
既にバス停がある場所には設置しないように注意する.
新しく設置するバス停の数は,$O(N \log N)$ で,ちゃんと計算すると,合計のバス停は $10000$ より小さくなる.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

#define ll long long
#define ull unsigned ll

template<class T>
struct ullHash{
  ull *key; T *val; unsigned memory, size, mask;

  void clear(){memset(val,0,size*sizeof(T));}
  void clear(int sz){size=1;while(size<sz)size*=2;mask=size-1;clear();}
  void init(int mem, int sz){memory=mem;size=1;while(size<sz)size*=2;mask=size-1;if(memory<size)memory=size;key=(ull*)malloc(memory*sizeof(ull));val=(T*)malloc(memory*sizeof(T));if(size)clear();}
  int function(ull a){return (a*97531)&mask;}
  T get(ull a){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;if(key[i]!=a) return 0;return val[i];}
  void set(ull a, T v){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;val[i]=v;}
  T increase(ull a, T v = 1){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;return val[i]+=v;}
};

ullHash<int> hash;

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 N;
int x[20000], y[20000];

int M;
int rx[20000], ry[20000];

void add_p(int ax, int ay){
  if(hash.get(ax*10000 + ay)==0){
    hash.increase(ax*10000 + ay);
    rx[M] = ax;
    ry[M] = ay;
    M++;
  }
}

void solve(int a, int b){
  int i, j, k;
  int ax, ay;
  int c = (a+b)/2, sz = b-a + 1;

  if(sz==1) return;
  if(sz==2){
    add_p(x[a], y[b]);
    return;
  }

  REP(i,a,b+1) add_p(x[c], y[i]);

  solve(a,c-1);
  solve(c+1,b);
}

int main(){
  int i, j, k;

  hash.init(50000, 50000);

  reader(&N);
  rep(i,N) reader(x+i,y+i);
  intIntSort(x,y,N);

  M = 0;
  rep(i,N) hash.increase(x[i] * 10000 + y[i]);
  solve(0, N-1);

  writer(M, '\n');
  rep(i,M){
    writer(rx[i], ' ');
    writer(ry[i], '\n');
  }

  return 0;
}

Current time: 2017年07月24日15時47分19秒
Last modified: 2014年08月06日01時45分30秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC024 ARC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: