AOJ2375 CarrotBreeding

• 問題

任意の2本を通る直線がちょうどn種類であるような最小の点の個数からなる点集合を出力せよ。

• 解法

まずk点が一般の位置にあるときk(k-1)/2本の直線が引ける。m個の点が同一直線上にあるとm(m-1)/2-1個直線が減るのでいい感じに直線を減らして目標の数にしたくてそういうことができる最小のkをとってきて頑張ってかたちを構成する。

直線を構成するような点の数はO(sqrt(k))個で目標の数が作れるけどkが小さいとうまく構成しないと点の数を超えるので小さい場合は具体例構成。(プログラム走らせてどういう場合が愚直にやるとアウトか調べた)

あとは適当に直線をなさないように余った点を配置して終了。ここは乱択した。

• 感想

発想は良問で場合分けは手元でやるので実装はやばくない感じです。N=7の場合の構成がかっこいい。

• コード

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<math.h>
#include<stdlib.h>
using namespace std;
int dp[2001];
int frm[2001];
vector<int>dat[2001];
#define SIZE 1000000000
typedef pair<int,int>pii;
vector<pii>get(int n)
{
	vector<pii>ret;
	if(n==2)
	{
		ret.push_back(make_pair(0,0));
		ret.push_back(make_pair(0,1));
		ret.push_back(make_pair(0,2));
		return ret;
	}
	if(n==4)
	{
		ret.push_back(make_pair(0,0));
		ret.push_back(make_pair(0,1));
		ret.push_back(make_pair(0,2));
		ret.push_back(make_pair(1,0));
		ret.push_back(make_pair(2,0));
		return ret;
	}
	if(n==5)
	{
		ret.push_back(make_pair(0,0));
		ret.push_back(make_pair(0,1));
		ret.push_back(make_pair(0,2));
		ret.push_back(make_pair(0,3));
		return ret;
	}
	if(n==6)
	{
		ret.push_back(make_pair(0,0));
		ret.push_back(make_pair(0,3));
		ret.push_back(make_pair(0,6));
		ret.push_back(make_pair(3,0));
		ret.push_back(make_pair(6,0));
		ret.push_back(make_pair(3,3));
		return ret;
	}
	if(n==7)
	{
		ret.push_back(make_pair(0,0));
		ret.push_back(make_pair(0,1));
		ret.push_back(make_pair(0,2));
		ret.push_back(make_pair(1,0));
		ret.push_back(make_pair(2,0));
		ret.push_back(make_pair(3,0));
		return ret;
	}
	if(n==8)
	{
		ret.push_back(make_pair(0,0));
		ret.push_back(make_pair(0,3));
		ret.push_back(make_pair(0,6));
		ret.push_back(make_pair(3,0));
		ret.push_back(make_pair(6,0));
		ret.push_back(make_pair(2,2));
		return ret;
	}
	if(n==12)
	{
		ret.push_back(make_pair(0,0));
		ret.push_back(make_pair(0,3));
		ret.push_back(make_pair(0,6));
		ret.push_back(make_pair(3,0));
		ret.push_back(make_pair(6,0));
		ret.push_back(make_pair(2,2));
		ret.push_back(make_pair(3,3));
		return ret;
	}
	for(int p=0;p<dat[n].size();p++)
	{
		if(p==0)
		{
			for(int i=0;i<dat[n][p];i++)
			{
				ret.push_back(make_pair(0,SIZE/2+i));
			}
		}
		if(p==1)
		{
			for(int i=0;i<dat[n][p];i++)
			{
				ret.push_back(make_pair(SIZE,SIZE/2+i));
			}
		}
		if(p==2)
		{
			for(int i=0;i<dat[n][p];i++)
			{
				ret.push_back(make_pair(SIZE/2+i,0));
			}
		}
		if(p==3)
		{
			for(int i=0;i<dat[n][p];i++)
			{
				ret.push_back(make_pair(SIZE/2+i,SIZE));
			}
		}
		if(p==4)
		{
			for(int i=0;i<dat[n][p];i++)
			{
				ret.push_back(make_pair(1+i,1+SIZE*2/3+i));
			}
		}
	}
	return ret;
}
int gcd(int a,int b)
{
	if(a==0)return b;
	if(b==0)return a;
	for(;;)
	{
		if(a<b)swap(a,b);
		a%=b;
		if(a==0)return b;
	}
}
int main()
{
	fill(dp,dp+2001,1000000000);
	dp[0]=0;
	for(int i=0;i<=2000;i++)
	{
		for(int j=3;j<70;j++)
		{
			if(i+(j*(j-1)/2-1)<=2000)
			{
				if(dp[i+(j*(j-1)/2-1)]>dp[i]+j)
				{
					dp[i+(j*(j-1)/2-1)]=dp[i]+j;
					frm[i+(j*(j-1)/2-1)]=j;
				}
			}
		}
	}
	for(int i=2;i<=2000;i++)
	{
		int now=i;
		for(;;)
		{
			if(now==0)break;
			dat[i].push_back(frm[now]);
			now-=(frm[now]*(frm[now]-1)/2-1);
		}
	}
	int mok;
	scanf("%d",&mok);
	if(mok==1)
	{
		printf("2\n0 0\n0 1\n");
		return 0;
	}
	if(mok==2)
	{
		printf("-1\n");
		return 0;
	}
	int num=-1;
	for(int i=3;;i++)
	{
		if(i*(i-1)/2>=mok&&i*(i-1)/2!=mok+1&&i*(i-1)/2!=mok+3)
		{
			num=i;
			break;
		}
	}
	int dec=num*(num-1)/2-mok;
	vector<pii>now=get(dec);
	for(int p=now.size();p<num;p++)
	{
		for(;;)
		{
			pii zan=make_pair(abs(rand()*rand()+rand())%SIZE,abs(rand()*rand()+rand())%SIZE);
			set<pii>se;
			bool f=true;
			for(int i=0;i<now.size();i++)
			{
				if(zan==now[i])
				{
					f=false;
					break;
				}
				pii v=make_pair(now[i].first-zan.first,now[i].second-zan.second);
				if(v.first<0)
				{
					v.first=-v.first;
					v.second=-v.second;
				}
				if(v.first==0)
				{
					v.second=abs(v.second);
				}
				int g=gcd(abs(v.first),abs(v.second));
				v.first/=g;
				v.second/=g;
				if(se.find(v)!=se.end())
				{
					f=false;
					break;
				}
			}
			if(f)
			{
				now.push_back(zan);
				break;
			}
		}
	}
	printf("%d\n",num);
	for(int i=0;i<now.size();i++)
	{
		printf("%d %d\n",now[i].first,now[i].second);
	}
}