分治法：巨人与鬼

一组n个巨人正与n个鬼进行战斗,每个巨人的武器是一个质子炮, 它可以把一串质子流射中鬼而把鬼消灭。

质子流沿直线行进,在击中鬼时就终止。巨人决定采取下述策略。他们寻找鬼配对,以形成n个巨人─鬼对,。

然后每个巨人同时向他选取的鬼射出一串质子流。我们知道,让质子流互相交叉是很危险的。

因此巨人选择的配对方式应该使质子流都不会交叉。假定每个巨人和每个鬼的位置都是平面上的一个固定点,并且没有三个位置共线, 求一种配对方案

  1 /*************************************************************************
  2     > File Name:my_jurenyugui.cpp
  3     > Author:chudongfang 
  4     > Mail:1149669942@qq.com 
  5     > Created Time: 2016年06月1日 星期三5 16时43分32秒
  6  ************************************************************************/
  7  
  8 #include<iostream>
  9 #include<stdio.h>
 10 #include<string.h>
 11 #include<math.h>
 12 #include<stdlib.h>
 13 using namespace std;
 14 typedef long long ll;
 15  
 16 typedef struct node
 17 {
 18     int id;
 19     int x;
 20     int y;
 21     int type;
 22     double angle; 
 23 }NODE;
 24 NODE p[1000];//结构体数组，用来储存每个人的信息
 25 int ans[1000];//结构，ans[i]=j代表编号i和编号为j的相连
 26 void sovel(int l,int r);
 27  
 28 int main(int argc, char const *argv[])
 29 {
 30     memset(ans,0,sizeof(ans));
 31     int x,y,t,len=1;
 32     while(scanf("%d%d%d",&t,&x,&y)!=EOF)// 录入数据 
 33     {
 34         p[len].x   =x;
 35         p[len].y   =y;
 36         p[len].id  =len;//对应ID
 37         if(t==1)
 38             p[len].type=1;//表示类型
 39         else
 40             p[len].type=-1;    
 41         len++;
 42     }        
 43     len--;
 44  
 45     sovel(1,len);
 46     
 47     for(int i=1;i<=len;i++)
 48         printf("%d ",ans[i]);
 49     return 0;
 50 }
 51  
 52 void sovel(int l,int r)//递归求解，分治思想
 53 {
 54     NODE t;
 55     if(l>=r)  return ;
 56     int pos=l;//初始化为第一个
 57     /************步骤1**************/
 58     for(int i=l+1;i<=r;i++)//找编号l-r区域内左下角节点
 59         if(p[i].y<p[pos].y||p[i].y==p[pos].y&&p[i].x<p[pos].x)
 60             pos=i;
 61  
 62     t=p[l];//交换
 63     p[l]=p[pos];
 64     p[pos]=t;
 65  
 66     int cnt=p[l].type;//从第一个开始
 67     /**************步骤2*************/
 68     for(int i=l+1;i<=r;i++)//计算点与左下角点的角度大小
 69         p[i].angle=atan2(p[i].y-p[l].y, p[i].x-p[l].x);
 70     
 71     /*for(int i=l;i<=r;i++)
 72     {
 73         printf("%d %d %d %lf
",p[i].id,p[i].x,p[i].y,p[i].angle);
 74     }*/
 75     
 76     for(int i=l+1;i<=r;i++)//按角度大小，把除左下角的元素排序
 77     {
 78         for(int j=i;j<=r;j++)
 79         {
 80             if(p[i].angle>p[j].angle)
 81             {
 82                 t=p[i];
 83                 p[i]=p[j];
 84                 p[j]=t;
 85             }
 86         }
 87     }
 88     
 89     /*for(int i=l;i<=r;i++)
 90     {
 91         printf("%d %d %d %lf
",p[i].id,p[i].x,p[i].y,p[i].angle);
 92     }*/
 93     /**************步骤3***************/
 94     for(int i=l+1;i<=r;i++)//排序后，从小到大遍历
 95     {
 96         cnt+=p[i].type;
 97         if(cnt==0)//当遍历过后的区域巨人和鬼的数量相同时
 98         {
 99             ans[p[l].id]=p[i].id;//链接左下角点和当前点
100             ans[p[i].id]=p[l].id;
101             sovel(l+1,i-1);//分治，递归求解左边区域
102             sovel(i+1,r);//分治，递归求解右边区域
103             break;
104         }
105     }
106     return ;
107 }