本文共 1423 字，大约阅读时间需要 4 分钟。

:

题目大意：

一个人拿着激光枪站在坐标(x,y)处，周围有N个墙，墙的两端点坐标为（x0, y0, x1, y2）。这个人朝着某个方向开枪，激光可以穿过任意数量个墙。求最多一枪能够穿过几个墙？注意，如果激光正好在墙的一端擦边而过，也算穿过。

思路：

看下图，

把人站的坐标看做是坐标的原点，人的正东西向为x轴，南北为y轴，正东向为0度。

然后就可以分别计算每一个墙要朝着多少度范围内射击能射到。这样，问题就抽象成了“给n个闭区间，求某一点覆盖的区间最多”，和   一样的（《训练指南上的例题》）。

实现时要特别注意的一个地方就是，墙跨过了0度的时候，这时候要把墙分开按两个墙算，假如原来是【x， y】，就要变成【0，x】和【y，360】

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int MAXN = 510;const double PI = acos(-1.0);int n，x, y;struct Event{    double r;    int type;    bool operator<(const Event&rhs)const{        if(r != rhs.r) return r < rhs.r;        return type > rhs.type;    }}arr[2*MAXN];struct Line{    int x0,y0,x1,y1;}wall[MAXN];inline double getRadian(int x1, int y1){    // 特殊情况，点在坐标轴上    if(x==x1 && y1>y) return 90;    if(x==x1 && y1
        
         x) return 0; double tmp = atan((y1-y)*1.0/(x1-x)); if(tmp < 0) tmp = PI+tmp; // 在第1，2象限 if(y1 > y){ return tmp*180/PI; } // 在第3，4象限 return 180+tmp*180/PI;}int main(){ while(~scanf("%d", &n) && n){ for(int i=0; i
         
           r2) swap(r1, r2); if(r2-r1>=180){ double tmp = r2; r2 = r1; r1 = 0; arr[idx].r = r1; arr[idx++].type = 1; arr[idx].r = r2; arr[idx++].type = -1; r1 = tmp; r2 = 360; } arr[idx].r = r1; arr[idx++].type = 1; arr[idx].r = r2; arr[idx++].type = -1; } sort(arr, arr+idx); int cur=0, maxx=0; for(int i=0; i
          
           0) ++cur, maxx=max(maxx,cur); else --cur; } printf("%d\n", maxx); } return 0;}
          
         
        
       
      
     
    
   

转载地址：http://qszni.baihongyu.com/