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); } }