算法题：uva 10535 - Shooter

算法题：uva 10535 - Shooter2014-03-17 csdn博客 shuangde800题目大意：

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

思路：

看下图，

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

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

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

代码：

#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>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<y） return 270;if（y==y1 && x1<x） return 180;if（y==y1 && x1>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<n; ++i）scanf（"%d%d%d%d",&wall[i].x0,&wall[i].y0,&wall[i].x1,&wall[i].y1）; scanf（"%d%d",&x,&y）; int idx = 0;// 转换为弧度区间for（int i=0; i<n; ++i）{double r1 = getRadian（wall[i].x0, wall[i].y0）;double r2 = getRadian（wall[i].x1, wall[i].y1）;if（r1 > 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<idx; ++i）{if（arr[i].type>0） ++cur, maxx=max（maxx,cur）;else --cur;}printf（"%d
", maxx）;}return 0;}