ZOJ 3379 Master Spark-白红宇

ZOJ 3379 Master Spark

阅读量：5962 次

发布时间：2019-06-19

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

计算出中轴能覆盖到某个点的极角范围，最大覆盖次数即是答案。

首先把中轴和点重合，此时中轴的角度为theta = atan(y/x)，

然后以原点为圆心旋转点和抛物线相交求出之间的夹角，

把x = a*y*y 化成极坐标下r cosθ = a *r *r (1 - cos²θ) ，解方程得到

极角范围应该为[theta-θ, theta+θ]。

有了极角范围，排序以后扫描线。

写的时候须小心的坑点：

1.theta-θ的范围可能超过[0, 2*pi]，需要取余。

2.取余以后有可能有end < begin的情况，需要在最左端手动添加事件点。

3.端点是都可以包括的，当极角相同时，入点事件优先于出点事件。

/**********************************************************            ------------------                          **   author AbyssFish                                     ***********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long double ld;const int maxn = 3e4+1;double x[maxn], y[maxn];inline ld sqr(ld x){ return x*x; }const ld DPI = acosl(-1)*2;typedef pair
                  
                    ev;#define fi first#define se secondvector
                   
                     evs;#define pb push_back//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif //cout<
                    
                      ::iterator it = evs.begin(); it != evs.end(); it++){ cur -= it->se; //cout<
                     
                      <