久々に重いMedium来たな。
https://community.topcoder.com/stat?c=problem_statement&pm=15376
問題
２次元座標上にいくつかの点がある。
ここで１つの直線を引くことを考える。
各点をこの直線上に射影し、その並びを考えよう。
並びが一致する一連の直線群は、同類である、と定義する。
また、並びがちょうど反転している場合も同類としよう。
正整数Nが与えられる。
直線群がちょうどN個に同類ごとに分類できるような点の集合を構成せよ。
解法
傾きが同じ直線は、その切片によらず同類になる。
さて、ここで２点の関係について考えてみる。
この２点の垂直二等分線に２点を射影すると両者は同じ位置に来る。
そこから傾きを少し変えると、それぞれの順番は左右どちらに傾けるかにより逆転する。
全頂点間における垂直二等分線を考える。
切片をずらした直線も同類になるので、例えば全部の線を原点を通るように並べ替えよう。
このとき直線の傾きがm個あるとする。
原点を中心とする単位円を、これらm個の直線で区切ることを考えよう。
直線との交点が2m個出来、直線間の円弧が2m個で計4m個の領域に分かれる。
射影後の並びが反転するものは同一視するという条件より、原点に対称な位置の領域を同一視すると2m個に分類できることになる。
ここまでわかると、いくつか点を配置し、２点を結んでできる直線の傾きがm通りであれば（垂直二等分線の傾きもm通りで）結果2m個の同類の分類できることがわかる。
なお、例外ケースは先に処理しておこう。
- Nが奇数の場合は解が無いが、N=1の場合は例外的に1点だけおけばよい。
- N=2の時は、適当に２点おけばよい。
- N=4は解なし。
- N=6はサンプルにある通り。
以後Nは8以上の整数とし、点を並べて傾きがN/2通りとなるようにしよう。
(0,y)と(1,z)にk個ずつ点を並べることにする。
(0,y)には(0,0)～(0,k-1)に等間隔に点を配置し、(1,z)には傾きを微調整しながら点を配置しよう。
そうすると2*k～(k^2+1)通りの傾きのいずれかを構築できる。
class OrthogonalProjections { public: vector <int> generate(int n) { if(n==1) return {0,0}; if(n==2) return {0,0,0,1}; if(n==6) return {0,0,0,1,1,2}; if(n%2 || n==4) return {}; int i,v=1; n=n/2-1; while(v*v<n) v++; vector<int> R; FOR(i,v) R.push_back(0),R.push_back(i); n-=2*v-1; R.push_back(1); R.push_back(0); int pre=0; FOR(i,v-1) { int x=min(n,v-1); pre+=x+1; n-=x; R.push_back(1); R.push_back(pre); } return R; } }
まとめ
考察は重いけど実装は軽いんだよな。
