巨人和鬼

一组n个巨人正与n个鬼进行战斗,每个巨人的武器是一个质子炮, 它可以把一串质子流射中鬼而把鬼消灭。质子流沿直线行进,在击中鬼时就终止。巨人决定采取下述策略。他们寻找鬼配对,以形成n个巨人─鬼对,。然后每个巨人同时向他选取的鬼射出一串质子流。我们知道,让质子流互相交叉是很危险的。因此巨人选择的配对方式应该使质子流都不会交叉。假定每个巨人和每个鬼的位置都是平面上的一个固定点,并且没有三个位置共线, 求一种配对方案。

解题思路：由题意知，其必存在一个解，这里利用分治的思想，利用一条线，把原区域分为两个区域，然后对这两个区域递归求解。

分割思路：

1.先找左下角节点

2.把其余点按其与左下角节点角度大小排序

3.从小到大遍历，当一边的巨人与鬼的数量相同时(这里利用正负1相加为0判断)，储存答案，递归求解

分割图如下：

用p1 –p6分割

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node {int biao, x, y;//序号和坐标bool id;//标识巨人还是鬼
};
int n;
node p[1000],ji;
int ans[1000];
bool cmp(node &a, node &b) {return a.y != b.y ? a.y < b.y : a.x < b.x;
}
bool cmp1(node &a, node &b) {return (atan2((a.y - ji.y),(a.x - ji.x))<atan2((b.y - ji.y),(b.x - ji.x)));
}
void go(int l,int r) {if (l > r)return;sort(p + l, p + r + 1, cmp);//获取最左下的点作为基点ji = p[l];sort(p + l + 1, p + r + 1, cmp1);//根据其他点与基点连线和水平线的角度进行排序int c1 = 0, c2 = 0;int k = r;while (!(ji.id != p[k].id&&c1 == c2)) {if (p[k].id == ji.id)c1++;//c1是相同标识的数量else c2++;//c2是与基点不同标识的数量k--;}ans[p[k].biao] = ji.biao;//只有当c1与c2的数量相等且基点与当前点标识不同时才能配对ans[ji.biao] = p[k].biao;go(l + 1, k - 1);//左半部分go(k + 1, r);//右半部份
}
int main(void) {while (cin >> n) {for (int i = 1; i <= n; i++) {cin >> p[i].x >> p[i].y >> p[i].id;p[i].biao = i;}go(1, n);for (int i = 1; i <= n; i++)cout << ans[i]<<" ";}system("pause");
}