算法竞赛入门经典第八章 巨人与鬼问题（点配对问题）详细图解 C++_巨人与鬼题目

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

说了这么多，其实题目就是平面上有偶数个点，两两配对并连线，找出连线不相交的配对方法。给出一组数据（3，4），（-9，0），（0，-5），（9，5），（-9，2），（-9，1），（0,，0），（-3，6）。我们让巨人排在前面，鬼排在后面，也就是前四个数和后四个数配对，如下图，黑色表示巨人，红色表示鬼。

想要两两配对不想交，首先要找到位置最低的一个点（如果y相同，则找x最小的），可以看出来是点3。如果让点3和所有点连线，观察它们与水平线形成的角度，我们发现角度最小的连线，即3和6连线，对剩下的点不会造成任何影响，接下来还可以用同样的方式解决剩下的点：找到最低的点2，与7连线角度最小，然后5与1连线，8与4连线，如图。

接下来我们让点的排列更一般，更换点1和点6的身份，同样地，找到y最低或y相同但x最小的点，点3，接下来每个点都与3连线：

发现找到与点3成角最小的点是巨人，而3和1是不能连线的，怎么办？我们继续按角度从小到大找，现在已经检查了3和1两个巨人，接下来找到点4，又是巨人，找到点6，现在有3个巨人和一个鬼，这时候什么都做不了，我们需要继续检查，接下来是点7和点8，此时我们检查了3个巨人和3个鬼。当检查的巨人和鬼数量相同，就是我们该做些什么的时候了。将3和8连线，发现连上了3和8，刚好将整个区域分成两部分，检查过的1号，4号，6号和7号点，以及未检查过的2号和5号点。而3号和8号的连线，不会影响两个区域的连线，左右两个区域完全可以配对。

接下来用同样的方式递归解决左右两个区域，比如对右侧区域，找到最低点7号（虽然7号和1号y相同，但7号x更小），按照角度检查找到1号点，可以直接配对，顺便说一下，目前我们提到的“角度”为极角，C/C++计算极角可以用库函数atan2(int y, int x)，包括在头文件math.h里。两个角(x1,y1)和(x2,y2）所成的角度计算可以用atan2(y1-y2, x1-x2)。
因此我们有了基本的算法：

1. 将所有点排序，找到y最小的点p，如果有一个以上y最小的点，找到其中x最小的点。
2. 剩下的点按照与点p所成极角排序。
3. 按照极角从小到大逐个检查，当检查过的（包括p点）巨人和鬼数量相同时：
   3a. p点和当前点（一定是一个巨人和一个鬼）的编号存入结果
   3b. 递归计算p点与当前点连线的左右两个区域。

我们发现每个点需要保存的信息很多，所以建立一个struct，保存每个点的x值，y值，id, 种类（type，巨人还是鬼），极角计算函数，并且在struct里面重载运算符<，可以方便地按照y值排序。struct外还需要一个按照极角排列的排序函数。
先看一下结果：

代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

struct Point
1
2
3
4
5
6
7