1 边界和湖心小岛分别算一个节点，，连接所有距离小于D的鳄鱼，时间复杂度O(N2)
2 判断每个连通图的节点中是否包含边界和湖心小岛，是则Yes否则No
3 冗长混乱的函数参数
#include <stdio.h>#include <malloc.h>#include <queue>#include <math.h>using namespace std;struct Coordinate{float x;float y;};bool operator==(Coordinate& a, Coordinate& b){return a.x == b.x && a.y == b.y;}float DistanceOfPoints(const Coordinate& a, const Coordinate& b){return sqrtf(pow(a.x – b.x, 2) + pow(a.y – b.y, 2));}void JudgePosition(const int& D, Coordinate* crocodile, const int& i, bool* isCloseToEdge, bool* isCloseToCenter){// 靠近湖岸if (crocodile[i].x >= 50 – D || crocodile[i].x <= -50 + D ||crocodile[i].y >= 50 – D || crocodile[i].y <= -50 + D){isCloseToEdge[i] = true;}else{isCloseToEdge[i] = false;}// 靠近湖心小岛if ( sqrtf(pow(crocodile[i].x, 2) + pow(crocodile[i].y, 2)) <= 7.5 + D){isCloseToCenter[i] = true;}else{isCloseToCenter[i] = false;}}bool IsCloseToEdge(const int& D, const Coordinate& crocodile){return (crocodile.x >= 50 – D || crocodile.x <= -50 + D ||crocodile.y >= 50 – D || crocodile.y <= -50 + D);}bool IsCloseToCenter(const int& D, const Coordinate& crocodile){return (sqrtf(pow(crocodile.x, 2) + pow(crocodile.y, 2)) <= 7.5 + D);}int* CreateMatrixGraph(const int& N){int* graph = (int*) malloc(sizeof(int) * N * N);for (int i = 0;i < N * N; i++){graph[i] = 0;}return graph;}bool IsMatrixConnected(const int& a, const int& b, int* graph, const int& N){if (a == b){return false;}return (graph[a * N + b]);}void MatrixConnect(const int& a, const int& b, int* graph, const int& N){if (IsMatrixConnected(a, b, graph, N)){printf("ERROR : %d AND %d ALREADY CONNECTED\n", a, b);return;}if (a == b){printf("ERROR : THE SAME VERTICE\n");return;}graph[a * N + b] = 1;graph[b * N + a] = 1;}void GetAdjoinVertice(const int& vertice, int* graph, int* adjoinVertice, int N){int currentIndex = 0;for (int i = 0; i < N; i++){if (graph[vertice * N + i] == 1){adjoinVertice[currentIndex++] = i;}}}void DFS(int* graph, const int& vertice, bool* isVisited, int N, bool* result){//printf("%d ", vertice);isVisited[vertice] = true;if (vertice == N – 2){result[0] = true;}if (vertice == N – 1){result[1] = true;}int* adjoinVertice = (int*) malloc(sizeof(int) * N);for (int i = 0; i < N; i++){adjoinVertice[i] = -1;}GetAdjoinVertice(vertice, graph, adjoinVertice, N);int i = 0;while (adjoinVertice[i] != -1){if (!isVisited[adjoinVertice[i]] /*&& DistanceOfPoints(crocodile[vertice], crocodile[i]) <= D*/){DFS(graph, adjoinVertice[i], isVisited, N, result);}i++;}free(adjoinVertice);}void BFS(int* graph, int vertice, bool* isVisited, int N){queue<int> t;t.push(vertice);isVisited[vertice] = true;while (!t.empty()){int currentVertice = t.front();t.pop();printf("%d ", currentVertice);int* adjoinVertice = (int*) malloc(sizeof(int) * N);for (int i = 0; i < N; i++){adjoinVertice[i] = -1;}GetAdjoinVertice(currentVertice, graph, adjoinVertice, N);int i = 0;while (adjoinVertice[i] != -1){if (!isVisited[adjoinVertice[i]]){t.push(adjoinVertice[i]);isVisited[adjoinVertice[i]] = true;}i++;}}}bool MatrixComponentsSearch(int* graph, bool* isVisited, int N, bool* result, int function = 1){for (int i = 0; i < N; i++){if (!isVisited[i]){if (function == 1){//printf("{ ");DFS(graph, i, isVisited, N, result);if (result[0] == true && result[1] == true){return true;}result[0] = false;result[1] = false;}else{//printf("{ ");BFS(graph, i, isVisited, N);//printf("}\n");}}}return false;}int main(void){int N;int D;scanf("%d %d", &N, &D);int nodeCount = N + 2;Coordinate* crocodile = (Coordinate*) malloc(sizeof(Coordinate) * nodeCount);bool* isVisited = (bool*) malloc(sizeof(bool) * N);for (int i = 0; i < N; i++){scanf("%f %f", &crocodile[i].x, &crocodile[i].y);}crocodile[N].x = 0;crocodile[N].y = 0;crocodile[N + 1].x = -1;crocodile[N + 1].y = -1;// 一共N个鳄鱼，N是湖心小岛，N+1是岸边int* graph = CreateMatrixGraph(N + 2);// 连接距离小于D的鳄鱼for (int i = 0; i < N; i++){if (IsCloseToCenter(D, crocodile[i])){MatrixConnect(i, N, graph, nodeCount);}if (IsCloseToEdge(D, crocodile[i])){MatrixConnect(i, N + 1, graph, nodeCount);}for (int j = i + 1; j < N; j++){if (DistanceOfPoints(crocodile[i], crocodile[j]) <= D){MatrixConnect(i, j, graph, nodeCount);}}}bool result[2];result[0] = false;result[1] = false;if (MatrixComponentsSearch(graph, isVisited, nodeCount, result)){printf("Yes");}else{printf("No");}return 0;}
学习会使你永远立于不败之地。
