HDU 6080 度度熊保护村庄(计算几何+floyd)
Problem Description
哗啦啦村袭击了喵哈哈村！
度度熊为了拯救喵哈哈村，带着自己的伙伴去救援喵哈哈村去了！度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地，牢牢的守住了喵哈哈村。
但是度度熊发现，这是一场旷日持久的战斗，所以度度熊决定要以逸待劳，保存尽量多的体力，去迎战哗啦啦村的战士。
于是度度熊决定派尽量多的人去休息，但是同时也不能松懈对喵哈哈村的保护。
换句话而言，度度熊希望尽量多的人休息，而且存在一个包围圈由剩下的人组成，且能够恰好的包围住喵哈哈村的所有住房（包括边界）。
请问最多能让多少个人休息呢？
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
Source
2017”百度之星”程序设计大赛 - 资格赛
Solution
这题是“百度之星”资格赛的第一题。虽然说我没有参加，但是听说这题貌似是通过次数最少的一题。
一开始看到题就想计算几何，题目要求一个凸包，使其能包围住另一个凸包，并要求该凸包上点数最少。我就开始想凸包和半平面有关的知识。首先被包围的点肯定只用管凸包，外面那一圈必然是凸的(凹的浪费)，于是就更坚定地想先求出里面的凸包，再在凸包外围搞事情，构造出另一个来，完全没有想其他什么算法。然后就搞不出来。。。
没想到，正解居然是图论，用floyd求最小环。上面纯计几的瓶颈就在于如何构造出外面的包围圈并使其周长最小(注意是周长不是面积)。在看了别人的博客后恍然大悟：直接构图连边用floyd求最小环！内部的凸包都不用求了，直接叉积判断方向！就是说一个环，按顺序转一圈，内部的点必在所有边的同一侧。于是我们就让内部的点在左侧，对外围的每个点对，构出向量，然后判断是否所有的点都在其左侧，是就连一条有向边，共线连双向边。然后就用floyd算法求最小环就行了。就是求自己到自己的最短路，一开始
好像很简单，为毛我这个智障就想不到呢？
时间复杂度但实测62MS，跑得比香港记者还快。。)
Code
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define N 520
using namespace std;
int n, m, ans, dp[N][N];
struct Point{
int x, y;
Point() {}
Point(int _x, int _y):x(_x), y(_y) {}
friend Point operator - (Point A, Point B){return Point(A.x - B.x, A.y - B.y);}
}hou[N], fri[N];
int Det(Point A, Point B){return A.x * B.y - A.y * B.x;}
int main(){
freopen("hdu6080.in", "r", stdin);
freopen("hdu6080.out", "w", stdout);
while(~ scanf("%d", &n)){
for(int i = 1; i <= n; i++) scanf("%d%d", &hou[i].x, &hou[i].y);
scanf("%d", &m);
for(int i = 1; i <= m; i++) scanf("%d%d", &fri[i].x, &fri[i].y);
for(int i = 1; i <= m; i++)
for(int j = 1; j <= m; j++){
dp[i][j] = -1;
if(i == j) continue;
bool ok = true;
for(int k = 1; k <= n; k++)
if(Det(hou[k] - fri[i], fri[j] - fri[i]) > 0){
ok = false;
break;
}
if(ok) dp[i][j] = 1;
}
for(int k = 1; k <= m; k++)
for(int i = 1; i <= m; i++){
if(dp[i][k] == -1) continue;
for(int j = 1; j <= m; j++){
if(dp[k][j] == -1) continue;
if(dp[i][j] == -1 || dp[i][k] + dp[k][j] < dp[i][j]) dp[i][j] = dp[i][k] + dp[k][j];
}
}
ans = -1;
for(int i = 1; i <= m; i++){
if(dp[i][i] == -1) continue;
if(ans == -1 || dp[i][i] < ans) ans = dp[i][i];
}
if(ans == -1) puts("ToT");
else printf("%d\n", m - ans);
}
return 0;
}明明是相同味道的花
为什么颜色却不一样