これ実装は簡単なので、解説有だと★5にしてはだいぶ楽なんだけど、あまり解かれていないな。
https://yukicoder.me/problems/no/869
問題
整数N,A,Bが与えられる。
2次元座標上で、(格子点でなくてもよいので)以下の条件を満たすようN個の頂点を配置せよ。
- 頂点対のうち点の距離が10以下となるのがA通り
- 頂点対のうち点の距離が20以下となるのがB通り
解法
乱数を使って微調整することを考える。
まず、y座標=0のところにU個、y座標=YのところにV個点を配置するとする。
この際、U+V=Nで、かつYは10より大きいとする。
とすると、距離が10以下となる頂点対は前者のグループ同士か後者のグループ同士になる。
これらを適当に配置しよう。
まず両グループそれぞれのX座標について考える。
先に0~0.0001以下の乱数列Tを生成しておく。
i番目の点とi+1番目の点は、R+T[i]個X座標が離れる、という配置にすることとし、距離10以下の点がA組となるようなRを二分探索する。
この際、入力のAの条件より、両グループのX座標の範囲は20以下に収まる。
すなわち、同グループ内の頂点は必ず距離が20以下である。
次にY座標を適切に設定することで、距離20以下の点がB個となるよう調整しよう。
これは二分探索でもいいし、両グループの頂点間で、距離が20となるようなY座標の候補を列挙し、ソートしてもよい。
ここで乱数を使ったのが活きてきて、Y座標の候補はU*V通りあるがちゃんと乱数を散らせばこれらは異なる値になるので、必ず条件を満たすY座標の値がある。
int N,A,B; long double getrandom() { int a=rand()%10000; int b=rand()%10000; return (a*10000+b)/10000000000.0; } vector<long double> hoge(int n,int p) { vector<long double> T; T.push_back(getrandom()); while(T.size()<n) T.push_back(T.back()+getrandom()); if(n<2) return T; long double L=0,R=17.3/(n-1); int i,x,y; FOR(i,100) { long double M=(L+R)/2.0; int num=0; FOR(y,n) FOR(x,y) if((T[y]+y*M)-(T[x]+x*M)<=10) num++; if(num>=p) L=M; else R=M; } FOR(i,n) T[i]+=L*i; return T; } void solve() { int i,j,k,l,r,x,y; string s; srand(time(NULL)); cin>>N>>A>>B; int U,V; for(U=1;U<=N;U++) { V=N-U; if(U>=V && U*(U-1)/2+V*(V-1)/2>=A) break; } x=A*1.0*U*(U-1)/(U*(U-1)+V*(V-1))+0.5; y=A-x; B-=U*(U-1)/2+V*(V-1)/2; vector<long double> S=hoge(U,x); vector<long double> T=hoge(V,y); vector<pair<long double,long double>> R; vector<double> C; FORR(s,S) FORR(t,T) { C.push_back(sqrt((long double)400-(t-s)*(t-s))-0.000000001); } sort(ALL(C)); reverse(ALL(C)); FORR(s,S) R.push_back({s,C[B-1]}); FORR(t,T) R.push_back({t,0}); /* int num[2]={}; FORR(x,R) FORR(y,R) if(x<y) { long double a=x.first-y.first; long double b=x.second-y.second; if(a*a+b*b<=100.0000000000) num[0]++; if(a*a+b*b<=400.0000000000) num[1]++; } _P("%d %d %d\n",N,num[0],num[1]); assert(num[0]==A); assert(num[1]==B+U*(U-1)/2+V*(V-1)/2); */ FORR(r,R) _P("%.12lf %.12lf\n",(double)r.first,(double)r.second); }
まとめ
乱数を微調整に使うのが面白いな。