AOJ0265 ねこまっしぐら

幾何ライブラリをちょっと整備したのでやってみた。解くたびにライブラリが増えるので生産性を感じる。

それっぽい点を全部列挙して適当な線分がちゃんと多角形の中にあるかを判定する。O(2^n*n^4)で前処理がO(n^6)なのでTLEはやばそうだけどちゃんとbreakするだけで通る。

ライブラリは省略します。ものぐさなので円関係のライブラリも一括で全部はってしまう。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
double eps=1e-9;
double pi=3.1415926535897932384626433832;
double inf=1e+100;
vector<P>dat[16];
bool isok[16][256][16];
//ライブラリ(省略)
int main()
{
	for(;;)
	{
		int num;
		scanf("%d",&num);
		if(num==0)break;
		vector<P>vec;
		for(int i=0;i<num;i++)
		{
			double za,zb;
			scanf("%lf%lf",&za,&zb);
			vec.push_back(P(za,zb));
		}
		for(int i=0;i<16;i++)for(int j=0;j<256;j++)for(int k=0;k<16;k++)isok[i][j][k]=false;
		for(int i=0;i<16;i++)dat[i].clear();
		for(int i=0;i<num;i++)
		{
			for(int j=0;j<num;j++)
			{
				for(int k=0;k<num;k++)
				{
					if(j==k)continue;
					if(fabs(det(vec[(i+1)%num]-vec[i],vec[k]-vec[j]))>eps)
					{
						P p=getcross(make_pair(vec[(i+1)%num],vec[i]),make_pair(vec[k],vec[j]));
						if(ison(make_pair(vec[(i+1)%num],vec[i]),p))
						{
							dat[i].push_back(p);
						}
					}
				}
			}
			dat[i].push_back(vec[i]);
			dat[i].push_back(vec[(i+1)%num]);
		}
		for(int i=0;i<num;i++)
		{
			vector<pair<double,int> >zv;
			for(int j=0;j<dat[i].size();j++)
			{
				zv.push_back(make_pair(abs(dat[i][j]-vec[i]),j));
			}
			sort(zv.begin(),zv.end());
			vector<P>z;
			P now=P(114514,1919893);
			for(int j=0;j<zv.size();j++)
			{
				if(abs(now-dat[i][zv[j].second])>eps)z.push_back(dat[i][zv[j].second]);
				now=dat[i][zv[j].second];
				//printf("%d  %lf %lf\n",i,z[j].x,z[j].y);
			}
			for(int j=0;j<z.size();j++)
			{
			//	printf("%d  %lf %lf\n",i,z[j].x,z[j].y);
			}
			dat[i]=z;
		}
		for(int i=0;i<num;i++)
		{
			for(int j=0;j<dat[i].size()-1;j++)
			{
				for(int k=0;k<num;k++)
				{
					//if(!isinside(vec,(((dat[i][j]+dat[i][j+1])/P(2,0))+vec[k])/P(2,0)))continue;
					vector<pair<double,int> >v;
					for(int l=0;l<num;l++)
					{
						if(ison(make_pair(vec[k],(dat[i][j]+dat[i][j+1])/P(2,0)),vec[l]))
						{
							v.push_back(make_pair(abs(vec[l]-vec[k]),l));
						}
					}
					v.push_back(make_pair(0,k));
					v.push_back(make_pair(abs((dat[i][j]+dat[i][j+1])/P(2,0)-vec[k]),-1));
					sort(v.begin(),v.end());
					vector<P>z;
					for(int l=0;l<v.size();l++)
					{
						if(v[l].second==-1)z.push_back((dat[i][j]+dat[i][j+1])/P(2,0));
						else z.push_back(vec[v[l].second]);
					}
					bool jud=true;
					for(int l=0;l<int(z.size())-1;l++)
					{
						bool fl=false;
						for(int m=0;m<vec.size();m++)
						{
							if(ison(make_pair(vec[(m+1)%num],vec[m]),(z[l]+z[l+1])/P(2,0)))
							{
								fl=true;
								break;
							}
						}
						if(!fl)
						{
							if(!isinside(vec,(z[l]+z[l+1])/P(2,0)))
							{
								jud=false;
								break;
							}
						}
					}
					for(int l=0;l<num;l++)
					{
						if(iscross(make_pair(vec[k],(dat[i][j]+dat[i][j+1])/P(2,0)),make_pair(vec[(l+1)%num],vec[l])))
						{
							jud=false;
							break;
						}
					}
					if(jud)
					{
						isok[i][j][k]=true;
						//printf("%d %d %d\n",i,j,k);
					}
				}
			}
		}
		int mini=100;
		for(int p=0;p<(1<<num);p++)
		{
			bool flag=true;
			for(int i=0;i<num;i++)
			{
				for(int j=0;j<dat[i].size()-1;j++)
				{
					bool f=false;
					for(int k=0;k<num;k++)
					{
						if((p&(1<<k))!=0)
						{
							if(isok[i][j][k])
							{
								f=true;
								break;
							}
						}
					}
					if(!f)
					{
						flag=false;
						break;
					}
				}
			}
			if(flag)
			{
				int cnt=0;
				for(int i=0;i<num;i++)
				{
					if((p&(1<<i))!=0)cnt++;
				}
				mini=min(mini,cnt);
				//if(cnt<=2)printf("%d\n",p);
			}
		}
		printf("%d\n",mini);
	}
}