tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 0265: Cats Going Straight

過去に二度挫折しています!!! 三度目の挑戦です!!!

それっぽい点を全部列挙してそれぞれの頂点に行くことができるか判定。
判定は、途中の点でさえぎられたら駄目、外に出たら駄目というのを判定する。
前者は線分の端点以外で交わるのを判定すればよい。
後者は、線分の端点で交わり、かつ直線として一致しないというものの交点を列挙して、それから始点と終点を加えてソート、隣り合う二つの中点がすべて多角形の中にあるかどうか判定すればよい。

強いライブラリをもっておくことと、それを使いこなすことが大事。
でもライブラリは省略、許してください。

#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const double EPS = 1e-5; //このEPSで通ったので、参考にしてください。
int n;
Pt pl[20];
int can[20][1100];
int main(){
	int a;
	while(scanf("%d",&a),a){
		n=a;
		for(int i=0;i<a;i++){
			double x,y;
			scanf("%lf%lf",&x,&y);
			pl[i]=Pt(x,y);
		}
		pl[a]=pl[0];
		vector<Pt>v;
		for(int i=0;i<a;i++){
			for(int j=i+1;j<a;j++){
				for(int k=0;k<a;k++){
					if(iLL(pl[i],pl[j],pl[k],pl[k+1])==1&&iLS(pl[i],pl[j],pl[k],pl[k+1])){
						v.push_back(pLL(pl[i],pl[j],pl[k],pl[k+1]));
					}
				}
			}
		}
		for(int i=0;i<a;i++)for(int j=0;j<v.size();j++)
			can[i][j]=0;
		for(int i=0;i<a;i++){
			for(int j=0;j<v.size();j++){
				bool ok=true;
				vector<Pt>tmp;
				tmp.push_back(pl[i]);
				tmp.push_back(v[j]);
				for(int k=0;k<a;k++){
					if(iSSstrict(pl[i],v[j],pl[k],pl[k+1])){ok=false;break;}
					if(iLL(pl[i],v[j],pl[k],pl[k+1])==1&&iSS(pl[i],v[j],pl[k],pl[k+1])){
						tmp.push_back(pLL(pl[i],v[j],pl[k],pl[k+1]));
					}
				}
				if(!ok)continue;
				std::sort(tmp.begin(),tmp.end());
				for(int k=0;k<tmp.size()-1;k++){
					if(sGP((tmp[k]+tmp[k+1])/2)==-1){ok=false;break;}
				}
				if(ok){
					can[i][j]=1;
			//		printf("(%f, %f) -> (%f, %f)\n",pl[i].x,pl[i].y,v[j].x,v[j].y);
				}
			}
		}
		int ret=a;
		for(int i=0;i<(1<<a);i++){
			bool ok=true;
			for(int j=0;j<v.size();j++){
				bool OK=false;
				for(int k=0;k<a;k++){
					if(i&(1<<k)){
						if(can[k][j])OK=true;
					}
				}
				if(!OK)ok=false;
			}
			if(ok)ret=min(ret,__builtin_popcount(i));
		}
		printf("%d\n",ret);
	}
}