计蒜之道初赛第三场--腾讯手机地图题解 |五十风的个人博客

题目大意是：在坐标系里给你n个扇形的半径、起始，结束度数，计算扇形覆盖的面积。如图：

（因为现在无法提交了，所以无法验证代码，若有错的地方请指正）这题首先要做的是对边的度数排序，不过是对所有度数排序，最开始想的时候只对扇形开始边的那个度数排序，写了半天一堆if else，后来突然想到了用所有边的度数排序。首先需要对输进去每每条边度数进行处理，我用的是这个结构体

struct DU
{
	int du;//度数
	int r;//当前度数所对应的半径
	bool if_end;//是否为扇形的结束边
	int num;//扇形编号
}a[MAX];

进行面积计算首先对a[]进行排序，接下来需要用到一些变量：一个set集合，记录扇形的半径；一个标记变量R，记录当前已有半径中最大的那个；记录起始，结束边的度数变量start,end；面积s；

struct SET_R
{
	int r;//半径
	int num;//半径对应的扇形
	 bool operator < (const dd &a) const
     {
		 return du<=a.du;
     }
};
set<SET_R> set_r;// 记录扇形的半径
set<SET_R>::iterator it;
int R;// 当前已有半径中最大的那个，即set_r.begin()
int start,end;// 起始，结束边的度数变量start,end
int s;
SET_R temp;

下面循环计算面积从小到大扫描边的度数： 1. set_r 不为空: 当前边半径r>=R，更新end，计算从start到end的面积，更新start；否则，更新start； 2. 更新set_r，遇到起始边把半径加入set_r，更新R；遇到结束边把此边对应半径从set_r删除，更新R

for(i=0;i<n;i++)
{
	if(set_r.empty()==false )
	{
		if(R<=a[i].r )//如果当前边的半径r>=R
		{
			end=a[i].du;//更新end
			s+=(end-start)*R*R*PI/360;//计算面积，注意需要对减法处理一下
			start=end;//更新start
		}
	}
	else
	{
		start=a[i].du;
	}

	//更新set_r
	temp.r=a[i].r;
	temp.num=a[i],num;
	if(a[i].if_end==false)
	{
		set_r.insert(temp);
	}
	else
	{
		set_r.erase(temp);
	}
	//更新R
	if(set_r.empty()==false)
	{
		it=set_r.begin();
		R=(*it).r;
	}
}

下面就以实际的例子来说明吧，这个例子包含了所有可能的情况。比如给的扇形是： 10 10 120 25 20 40 25 80 100 20 30 90 5 70 150 如图

对这组数进行整理后得到如下数组 (红色为结束边)

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

扫描[0] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为Set_r为空所以start=a[i].du 2 更新set_r


set_r	10

R=10；扫描[1] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为R<= a[i].r && set_r不空所以end=a[i].du S+=(end-start)*R*R*PI/360; //计算面积，注意需要对减法处理一下 Start=a[i].du 2 更新set_r


set_r	25	10

R=25；计算得到蓝色部分面积

扫描[2] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为R>a[i].r ，跳过 2 更新set_r


set_r	25	20	10

R=25；扫描[3] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为R<= a[i].r && set_r不空所以end=a[i].du S+=(end-start)*R*R*PI/360; //计算面积，注意需要对减法处理一下 Start=end 2 更新set_r


set_r	20	10

R=20；计算得到蓝色部分面积

扫描[4] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为R> a[i].r ，跳过 2 更新set_r


set_r	20	10	5

R=20 扫描[5] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为R<= a[i].r && set_r不空所以end=a[i].du S+=(end-start)*R*R*PI/360; //计算面积，注意需要对减法处理一下 Start=end 2 更新set_r


set_r	25	20	10	5

R=25；计算得到蓝色部分面积

扫描[6] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为R>a[i].r ，跳过 2 更新set_r


set_r	25	10	5

扫描[7] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为R<= a[i].r && set_r不空所以end=a[i].du S+=(end-start)*R*R*PI/360; //计算面积，注意需要对减法处理一下 Start=end 2 更新set_r


set_r	10	5

R=10；计算得到蓝色部分面积

扫描[8] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为R<= a[i].r && set_r不空所以end=a[i].du S+=(end-start)*R*R*PI/360; //计算面积，注意需要对减法处理一下 Start=end 2 更新set_r


set_r	5

R=5；计算得到蓝色部分面积

扫描[9] 1

	0	1	2	3	4	5	6	7	8	9
度数	10	20	30	40	70	80	90	100	120	150
半径	10	25	20	25	5	25	20	25	10	5

因为R<= a[i].r && set_r不空所以end=a[i].du S+=(end-start)*R*R*PI/360; //计算面积，注意需要对减法处理一下 Start=end 2 更新set_r


set_r

计算得到蓝色部分面积

计蒜之道 初赛 第三场--腾讯手机地图 题解

计蒜之道初赛第三场--腾讯手机地图题解