比赛的时候并没有做出这道题。。 于是在赛后决定更正一下
把度度熊和它的伙伴们当成黑点，所有的村庄当成红点 考虑对所有的黑点建图 O(n²)暴力枚举所有的黑点点对，对于每个点对(a, b)，O(n)检测所有红点 如果所有的红点都在点对(a, b)(a->b)的右侧，则a到b连接一条长度为1的单向边 如果所有的红点都在点对(a, b)(a->b)的左侧，则b到a连接一条长度为1的单向边 否则a和b不连边 （注意三点共线的时候，如果c点在a和b的线段上直接连双向边，否则不连边） 之后可以得到一张图G 很好想到图中最小的环就是最优方案，令road[a][b]为点a到点b的最短路 跑一边floyd就好了，答案就是黑点个数m-min(road[i][i]) (1<=i<=m) 当然如果这个图中都不存在环，那么说明无法保护整个村庄，输出ToT 复杂度O(n^3)，注意虽然n=500不过还有可能会超时。。优化下就好了
然后就可以了。。 至于怎么判断左右边，就是一个差积的问题啦。。 然后就没有了 感觉很妙啊。。 一开始我是想对全部点建一个凸包，然后跑。。 但我只yy到一个盘TOT的做法，至于点数，还真想不到
#include<cstdio> #include<cstring> const int N=505; const int MAX=1<<28; int n,m; struct Node{int x,y;}; Node a[N],b[N];//住房 士兵 int f[N][N]; int mymin (int x,int y){return x<y?x:y;} bool check (Node a,Node b,Node c)//a是否不在b，c的中间 { if (a.x>b.x&&a.x>c.x) return true; if (a.x<b.x&&a.x<c.x) return true; if (a.y>b.y&&a.y>c.y) return true; if (a.y<b.y&&a.y<c.y) return true; return false; } double mu (Node a,Node b,Node c) { double x1=a.x-c.x,y1=a.y-c.y; double x2=b.x-c.x,y2=b.y-c.y; return x1*y2-x2*y1; } int main() { while (scanf("%d",&n)!=EOF) { for (int u=1;u<=n;u++) scanf("%d%d",&a[u].x,&a[u].y); scanf("%d",&m); for (int u=1;u<=m;u++) scanf("%d%d",&b[u].x,&b[u].y); for (int u=1;u<=m;u++) for (int i=1;i<=m;i++) f[u][i]=MAX; for (int u=1;u<=m;u++) { for (int i=1;i<=m;i++) { bool tf=true; for (int k=1;k<=n;k++) { if (mu(a[k],b[i],b[u])<0)//左边 tf=false; if (mu(a[k],b[i],b[u])==0&&check(a[k],b[i],b[u])) tf=false; if (!tf) break; } if (tf) f[u][i]=1; } } for (int u=1;u<=m;u++) for (int i=1;i<=m;i++) { if (f[i][u]==MAX) continue; for (int j=1;j<=m;j++) f[i][j]=mymin(f[i][j],f[i][u]+f[u][j]); } int ans=MAX; for (int u=1;u<=m;u++) ans=mymin(ans,f[u][u]); if (ans>m) printf("ToT\n"); else printf("%d\n",m-ans); } return 0; }话说可以在hdu做了
