この記事は帰ってきた AOJ-ICPC Advent Calendar 2022の14日目の記事です。
問題概要
整数 $N$ が与えられます。 二次元座標上に $K$ 個の点 $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{K},y_{K})$ を以下の条件を満たすように置きます。
任意の $i$ に対して $0\leq x_{i}\leq 10^{9}$ かつ $0\leq y_{i}\leq 10^{9}$
2点以上通る点がちょうど $N$ 本
この条件を満たす最小の $K$ が存在するならその最小の $K$ とそのときの点を出力。
存在しないなら $-1$ を出力。
例
$N=5$ のとき
$N=6$ のとき
解法
$N$ が大きい場合を先に考えます。 まず、 $K$ 点の中から２つの点を選ぶ方法は $\frac{K^{2}-K}{2}$ 通りあるので、 $A$ を $N\leq \frac{A(A-1)}{2}$ を満たす最小の整数 $A$ とすると、 $A\leq K$ が成り立ちます。
ここで $R=\frac{A(A-1)}{2}-N$ とします。
$R=0$ のときは任意の $3$ 点が同一直線上に存在しなければいいです。
$R=2$ のときは同一直線上にある $3$ 点の組がちょうど1組だけ存在すれば良いです。
$R=5$ のときは同一直線上にある $4$ 点の組がちょうど1組だけ存在すれば良いです。
例えば、上に示した $N=5$ の例は $K=5$ なので何の施しもしないと $N=10$ となりますが、 $4$ 点を同一直線上に並べているので、 $N=10-5$ より 条件を満たすようにしています。
同じような操作をすることである状態から直線の数を $-2$ したり $-5$ したりすることは可能です。
よって、 $R=1,3$ 以外であれば $K=A$ が達成可能です。
凸$K$ 多角形の角を潰すイメージで増やしていくと効率よく(点を重複させながら)同一直線上にある点の組の数を増やしていくことができます。
$R=1,3$ のときは $K=A+1$ として、$-2,-5$ を繰り返すことで達成できます。
$N$ が小さいときは少し例外が出てきます
$N=2$ のとき そもそも達成できません
$N=7$ のとき $A=5,R=3$ なので、 $K=6$ です。
$\frac{K^{2}-K}{2}-N=8$ なので、 $6$ つの点で「同一直線上にちょうど3点が存在する直線」を $4$ つ作る必要があります。
これは後で示すどの方法でも構築するのが難しいので別途で作る必要があります。
以上を実装すればいいです。
実装方法
今回は凸多角形の角を潰すイメージで考えたので実際に凸多角形を作って、その辺上に点をおくことで同一直線上に $3$ つ以上の点が存在する直線を作ります。
例えば $N=29$ のときは $6$ 角形を $N=24$ のときは $4$ 角形を返す関数を用いて、辺上に点を挿入すればいいです。
$R$ の値によって、挿入する点の数や挿入される辺の数が異なりますが、例えば $R=11$ なら $(5,2,2,2)$ を返すような、和が $N$ になる、要素が $5,2$ のみの配列を用意しておけば実装が楽になります。
また、 凸$B$ 角形を作るところを、ランダムに $B$ 個の点 をとり、2点の間を結ぶ直線の間に点を挿入するというやり方でもできます。
前者のメリットは座標が $10^{6}$ 程度で抑えられるので、問題の制約が少し厳しくなっても大丈夫である点と決定的である点で、後者のメリットは実装が楽になる点です。
コード
#include <bits/stdc++.h> using namespace std; #define rep(i,a) for(int i=0;i<a;i++) #define all(p) p.begin(),p.end() int solve(int N); int main(){ int N; cin>>N; solve(N); } int solve(int N){ if(N==7){ cout<<"6\n0 0\n0 3\n3 0\n2 0\n1 2\n0 4\n"; return 0; } if(N==2){ cout<<"-1\n"; return 0; } if(N==1){ cout<<"2\n0 0\n1 1\n"; return 0; } //a個の点を返す auto f=[&](int a)->vector<pair<int,int>>{ /* //ランダムに返す random_device rd; default_random_engine eng(rd()); uniform_int_distribution<int> distr(0,16'666'665); vector<pair<int,int>> ans(a); rep(i,a){ ans[i].first=distr(eng)*6; ans[i].second=distr(eng)*6; } return ans; */ //凸多角形を返す if(a==3){ return {{12,0},{0,0},{0,12}}; } vector<pair<int,int>> order; rep(i,200) rep(j,i+1){ if((int)order.size()==a-2) break; if(__gcd(i,j)==1){ order.push_back({i,j}); } } sort(all(order),[&](pair<int,int> l,pair<int,int> r){ return l.first*r.second>l.second*r.first; }); int H=0; rep(i,a-2) H+=order[i].second; vector<pair<int,int>> ans={{0,0},{0,H}}; rep(i,a-2){ ans.push_back({ans[i+1].first+order[i].first,ans[i+1].second-order[i].second}); } for(auto &x:ans) x.first*=6,x.second*=6; return ans; }; //点lと点rをa:bで内分する点 auto g=[](pair<int,int> l,pair<int,int> r,int a,int b)->pair<int,int>{ swap(a,b); return {(b*l.first+a*r.first)/(a+b), (b*l.second+a*r.second)/(a+b)}; }; int A=1; while(N>(A*(A-1))/2) A++; int K=A; int M=(K*(K-1))/2; int R=M-N; if(R==1||R==3){ M+=K; R+=K; K++; } int a=K; vector<int> cou(K); rep(i,K){ if(R!=8&&R!=6&&R>=5){ cou[i]=2; a-=2; R-=5; }else if(R>=2){ cou[i]=1; a-=1; R-=2; } } auto p=f(a); p.push_back(p[0]); vector<pair<int,int>> ans; rep(i,a){ ans.push_back(p[i]); rep(j,cou[i]){ ans.push_back(g(p[i],p[i+1],j+1,cou[i]-j)); } } // output ans cout<<ans.size()<<"\n"; for(auto x:ans) cout<<x.first<<" "<<x.second<<"\n"; return 0; }
