#include #include #include using namespace std; const int maxn=510,maxm=510,INF=0x7fffffff; int x[maxn][2],y[maxm][2]; int adj[maxm][maxm],dist[maxm][maxm]; int n,m; //判断所有点是否在y[j]和y[k]构成的边大于0的一侧,小于0的一侧或者在直线上 void link(int j,int k){ int cnt1=0,cnt2=0,cnt3=0; int x1,y1,x2,y2,df; for(int i=0;i0){ if(cnt2>0)break; cnt1++; }else if(df<0){ if(cnt1>0)break; cnt2++; }else if(x1*x2<=0){ cnt3++; }else{ //需要剪枝,否则会超时 break; } } if(cnt3==n){ adj[j][k]=adj[k][j]=1; }else{ if(cnt1+cnt3==n){ adj[j][k]=1; } if(cnt2+cnt3==n){ adj[k][j]=1; } } } //如果点都在j->k大于0的一侧,建立一条j到k的边,反之建立k->j的边,如果都在k-j的边上,建立一条双向边 //这样建图的好处是,每一个环路必然包围x的点,建立的图包含所有可能包围x的环路 //从其中寻找最小环路即为答案 //求最小环路使用floyed算法即可 //floyed算法求解全局最短路,使用的是动态规划思想,遍历到点k时,dist[i][j]表示i到j不超过k的最短路径 //而最小环如果存在,且其中编号最大的点为k,相邻的点依次是i,j,那么最小环必然是adj[k][j]+adj[i][k]+dist_k[i][j] // 因此,只需要枚举所有可能的k,i,j取最小可得到答案,时间复杂度为O(n^3) //此外,也可以从任意的 // 在floyed算法期间前k-1轮,可求出dist_k[i][j],因此第k轮可求出固定k之下的最小值。 int floyed() { int ans=INF; for(int k=0;k