哗啦啦村袭击了喵哈哈村！
度度熊为了拯救喵哈哈村，带着自己的伙伴去救援喵哈哈村去了！度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地，牢牢的守住了喵哈哈村。
但是度度熊发现，这是一场旷日持久的战斗，所以度度熊决定要以逸待劳，保存尽量多的体力，去迎战哗啦啦村的战士。
于是度度熊决定派尽量多的人去休息，但是同时也不能松懈对喵哈哈村的保护。
换句话而言，度度熊希望尽量多的人休息，而且存在一个包围圈由剩下的人组成，且能够恰好的包围住喵哈哈村的所有住房（包括边界）。
请问最多能让多少个人休息呢？
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 2 1 1 2 2 4 0 0 0 4 4 2 4 0 1 1 1 2 0 0 0 1 Sample Output 1 ToT
把度度熊和它的伙伴们当成黑点，所有的村庄当成红点
考虑对所有的黑点建图
O(n²)暴力枚举所有的黑点点对，对于每个点对(a, b)，O(n)检测所有红点
如果所有的红点都在点对(a, b)(a->b)的右侧，则a到b连接一条长度为1的单向边
如果所有的红点都在点对(a, b)(a->b)的左侧，则b到a连接一条长度为1的单向边
否则a和b不连边
具体如何判定？假设当前便利到黑点a和b，红点为c
红点c在a和b(a->b)的右侧则有
同理大于0说明在左侧，等于0说明三点共线
（注意三点共线的时候，如果c点在a和b的线段上直接连双向边，否则不连边）
之后可以得到一张图G
很好想到图中最小的环就是最优方案，令road[a][b]为点a到点b的最短路
跑一边floyd就好了，答案就是黑点个数m-min(road[i][i]) (1<=i<=m)
当然如果这个图中都不存在环，那么说明无法保护整个村庄，输出ToT
复杂度O(n^3)，注意虽然n=500不过还有可能会超时。。优化下就好了
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define inf 1044266558 typedef struct Point { int x, y; Point operator - ( const Point &b ) const { Point c; c.x = x-b.x; c.y = y-b.y; return c; } double operator * ( const Point &b ) const { return x*b.y-y*b.x; } }Point; Point h[505], s[505]; int n, m, ans, road[505][505]; bool Jud(Point x, Point y, Point z) { if((x.x<z.x && y.x<z.x) || (x.y<z.y && y.y<z.y) || (x.x>z.x && y.x>z.x) || (x.y>z.y && y.y>z.y)) return 1; return 0; } int main(void) { int i, j, k, flag; while(scanf("%d", &n)!=EOF) { memset(road, 62, sizeof(road)); for(i=1;i<=n;i++) scanf("%d%d", &h[i].x, &h[i].y); scanf("%d", &m); for(i=1;i<=m;i++) scanf("%d%d", &s[i].x, &s[i].y); for(i=1;i<=m;i++) { for(j=1;j<=m;j++) { flag = 1; for(k=1;k<=n;k++) { if((s[i]-s[j])*(s[i]-h[k])<0 || (s[i]-s[j])*(s[i]-h[k])==0 && Jud(s[i], s[j], h[k])) { flag = 0; break; } } if(flag) road[i][j] = 1; } } ans = inf; for(k=1;k<=m;k++) { for(i=1;i<=m;i++) { if(road[i][k]==inf) continue; for(j=1;j<=m;j++) road[i][j] = min(road[i][j], road[i][k]+road[k][j]); } } for(i=1;i<=m;i++) ans = min(ans, road[i][i]); if(ans>m) printf("ToT\n"); else printf("%d\n", m-ans); } return 0; }
