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

分类: algorithm

2015-07-19

|

1152

|

评论:0

分享:

题目大意是:   在坐标系里给你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    

 

 
 

 

 
 

 

 
 

 

 
 

 

 
    计算得到蓝色部分面积                                



标签: 计蒜客
本文共 0 个回复

发表评论 (对文章评论)

captcha