哗啦啦村袭击了喵哈哈村！
度度熊为了拯救喵哈哈村，带着自己的伙伴去救援喵哈哈村去了！度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地，牢牢的守住了喵哈哈村。
但是度度熊发现，这是一场旷日持久的战斗，所以度度熊决定要以逸待劳，保存尽量多的体力，去迎战哗啦啦村的战士。
于是度度熊决定派尽量多的人去休息，但是同时也不能松懈对喵哈哈村的保护。
换句话而言，度度熊希望尽量多的人休息，而且存在一个包围圈由剩下的人组成，且能够恰好的包围住喵哈哈村的所有住房（包括边界）。
请问最多能让多少个人休息呢？
Input本题包含若干组测试数据。
第一行一个整数n，表示喵哈哈村的住房数量。
接下来n行，每行两个整数(x1[i],y1[i])，表示喵哈哈村的住房坐标。
第n+1行一个整数m，表示度度熊的士兵数量。
接下来m行，每行两个整数(x2[i],y2[i])，表示度度熊伙伴的坐标。
满足:
1<=n,m<=500
-10000<=x1[i],x2[i],y1[i],y2[i]<=10000
Output请输出最多的人员休息的数目。
如果无法保护整个村庄的话，输出"ToT"
Sample Input Copy 2 1 1 2 2 4 0 0 0 4 4 2 4 0 1 1 1 2 0 0 0 1 Sample Output Copy 1 ToTStatistic | Submit | Clarifications | Back
和做的：http://blog.csdn.net/haut_ykc/article/details/75571044一模一样。
按照凸包的思想求一发最小环就行了，详情看上边链接。。。。
#include<map> #include<stack> #include<queue> #include<vector> #include<math.h> #include<stdio.h> #include<iostream> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; typedef long long ll; #define inf 100000000 #define maxn 505 #define eps 1e-10 int d[maxn][maxn],n,m; struct node { int x,y; }a[maxn],b[maxn]; bool tepan()//所有点重合要特判掉 { int i; for(i=1;i<=n;i++) if(abs(a[i].x-a[1].x)>0 || abs(a[i].y-a[1].y)>0) return 0; for(i=1;i<=m;i++) if(abs(b[i].x-a[1].x)>0 || abs(b[i].y-a[1].y)>0) return 0; printf("%d\n",m-1); return 1; } int work(node a,node b, node c) { return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x); } bool judge(node x,node y)//判断呢些点是不是在这两点构成的线段上 { if(x.x>y.x) swap(x,y); for(int i=1;i<=n;i++) if(a[i].x<x.x || a[i].x>y.x) return 0; if(x.y>y.y) swap(x,y); for(int i=1;i<=n;i++) if(a[i].y<x.y || a[i].y>y.y) return 0; printf("%d\n",m-2); return 1; } int check(node x,node y) { int i,t1=0,t2=0; for(i=1;i<=n;i++) { int tmp=work(x,y,a[i]); if(tmp>0)//点在直线左侧 t1++; if(tmp<0)//点在直线右侧 t2++; if(t1 && t2)//该直线上这两点不是凸包上的点 return 0; } if(t1) return 1; if(t2) return 2; if(judge(x,y)) return -1; return 3; } void floyd() { int i,j,k,ans=inf; for(k=1;k<=m;k++) for(i=1;i<=m;i++) { if(d[i][k]==inf) continue; for(j=1;j<=m;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } for(i=1;i<=m;i++) ans=min(ans,d[i][i]); if(ans>=inf || ans<=2) printf("ToT\n"); else printf("%d\n",m-ans); } void solve() { int i,j; for(i=1;i<=m;i++) for(j=i+1;j<=m;j++) { int mark=check(b[i],b[j]); if(mark==-1) return; if(mark==1) d[i][j]=1; if(mark==2) d[j][i]=1; if(mark==3) d[i][j]=d[j][i]=1; } floyd(); } int main(void) { int i,j; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);//xx可忽略 scanf("%d",&m); for(i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y); for(i=1;i<=m;i++) for(j=1;j<=m;j++) d[i][j]=inf; if(tepan()) return 0; solve(); } return 0; }
