分治法——巨人与鬼问题

题意：在平面上有n个巨人和n个鬼，没有三者在同一条直线上。每个巨人需要选择一个不同的鬼，向其发送质子流消灭它。质子流由巨人发射，沿直线行进，遇到鬼后消失。由于质子流交叉是很危险的，所有质子流经过的线段不能有交点。请设计一种给巨人和鬼配对的方法。

分析：主要就是把图上的点分成两份，每份中鬼和巨人一样多，依次递归，并保证不能有交点。

第一步，先找y轴最小的点，其次是x轴最小，按这个点为原点，划极坐标，从（0，），开始找直到找到相同数量的巨人和鬼停止。

第二步，连接巨人与鬼。剩下再进行分治递归。

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;typedef struct node
{int id;int x;int y;int type;double angle;bool operator<(const node &t) {return angle < t.angle;}
}NODE;
NODE p[1000];//结构体数组，用来储存每个人的信息
int ans[1000];//结构，ans[i]=j代表编号i和编号为j的相连
void sovel(int l, int r);int main()
{memset(ans, 0, sizeof(ans));int x, y, t, len = 1;while (scanf("%d%d%d", &t, &x, &y) != EOF)// 录入数据 {p[len].x = x;p[len].y = y;p[len].id = len;//对应IDif (t == 1)p[len].type = 1;//表示类型elsep[len].type = -1;len++;}len--;sovel(1, len);for (int i = 1; i <= len; i++)printf("%d ", ans[i]);return 0;
}void sovel(int l, int r)//递归求解，分治思想
{NODE t;if (l >= r)  return;int pos = l;//初始化为第一个for (int i = l + 1; i <= r; i++)//找编号l-r区域内左下角节点if (p[i].y < p[pos].y || p[i].y == p[pos].y&&p[i].x < p[pos].x)pos = i;t = p[l];//交换p[l] = p[pos];p[pos] = t;int cnt = p[l].type;//从第一个开始for (int i = l + 1; i <= r; i++)//计算点与左下角点的角度大小p[i].angle = atan2(p[i].y - p[l].y, p[i].x - p[l].x);sort(p+l+1 , p + r+1);//以角度大小排序for (int i = l + 1; i <= r; i++){cnt += p[i].type;if (cnt == 0)//当遍历过后的区域巨人和鬼的数量相同时{ans[p[l].id] = p[i].id;//链接左下角点和当前点ans[p[i].id] = p[l].id;sovel(l + 1, i - 1);//分治，递归求解左边区域sovel(i + 1, r);//分治，递归求解右边区域break;}}return;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！