巨人和鬼
一组n个巨人正与n个鬼进行战斗,每个巨人的武器是一个质子炮, 它可以把一串质子流射中鬼而把鬼消灭。质子流沿直线行进,在击中鬼时就终止。巨人决定采取下述策略。他们寻找鬼配对,以形成n个巨人─鬼对,。然后每个巨人同时向他选取的鬼射出一串质子流。我们知道,让质子流互相交叉是很危险的。因此巨人选择的配对方式应该使质子流都不会交叉。假定每个巨人和每个鬼的位置都是平面上的一个固定点,并且没有三个位置共线, 求一种配对方案。
解题思路：由题意知，其必存在一个解，这里利用分治的思想，利用一条线，把原区域分为两个区域，然后对这两个区域递归求解。
分割思路：
1.先找左下角节点
2.把其余点按其与左下角节点角度大小排序
3.从小到大遍历，当一边的巨人与鬼的数量相同时(这里利用正负1相加为0判断)，储存答案，递归求解
分割图如下：
用p1 --p6分割
下面上代码(已加注释)：
/*************************************************************************
> File Name:my_jurenyugui.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月1日 星期三5 16时43分32秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef struct node
{
int id;
int x;
int y;
int type;
double angle;
}NODE;
NODE p[1000];//结构体数组，用来储存每个人的信息
int ans[1000];//结构，ans[i]=j代表编号i和编号为j的相连
void sovel(int l,int r);
int main(int argc, char const *argv[])
{
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;//对应ID
if(t==1)
p[len].type=1;//表示类型
else
p[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;//初始化为第一个
/************步骤1**************/
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;//从第一个开始
/**************步骤2*************/
for(int i=l+1;i<=r;i++)//计算点与左下角点的角度大小
p[i].angle=atan2(p[i].y-p[l].y, p[i].x-p[l].x);
/*for(int i=l;i<=r;i++)
{
printf("%d %d %d %lf\n",p[i].id,p[i].x,p[i].y,p[i].angle);
}*/
for(int i=l+1;i<=r;i++)//按角度大小，把除左下角的元素排序
{
for(int j=i;j<=r;j++)
{
if(p[i].angle>p[j].angle)
{
t=p[i];
p[i]=p[j];
p[j]=t;
}
}
}
/*for(int i=l;i<=r;i++)
{
printf("%d %d %d %lf\n",p[i].id,p[i].x,p[i].y,p[i].angle);
}*/
/**************步骤3***************/
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 ;
}
注意这里采用EOF为录入结束标志。windows下用ctrl+z linux下用ctrl+d
测试数据：
11 1
10 1
01 2
02 2
运行结果：
4 3 2 1