uva1606-白红宇

uva1606

阅读量：4114 次

发布时间：2019-05-25

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

题意：平面上有n个点，每个点都是黑点或者是白点，现在需要防止一条隔板，使得隔板一侧的白点数加上另一侧的黑点数总数最大，隔板上的点可以看做是在任意一侧；

分析：

可以先枚举一个基准点，然后将一条直线绕着这个点旋转，每当直线扫过一个点就可以动态维护，每个点最多被扫描到两次

在这里我们使用atan2和叉积，用叉积来判断两条直线的角度，用atan2来算极角

代码如下：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      using namespace std;#define me(s) memset(s,0,sizeof(s))#define rep(i,n) for(int i=0;i<(n);i++)typedef long long ll;typedef unsigned int uint;typedef unsigned long long ull;typedef pair 
                      
                        P;const int N=1000+5;struct Point{ int x,y; double rad; bool operator<(const Point&rhs)const { return rad
                       
                        =0;}int solve(){ if(n<=2)return 2; int ans=0; for(int i=0;i
                        
                         =k才停止 { if(R==L){R=(R+1)%k;cnt++;} //空区域，暂时多计入一个点，最后舍去 while(R!=L&&Left(p[L],p[R])) //扫描线一直逆时针旋转，直到旋转角度刚刚>180度停止统计 { R=(R+1)%k; cnt++; } cnt--; //舍去多计入的点，也可以理解为由于分隔线的旋转，原来在分隔线上的点现在变为了右侧的点，要减掉一个 L++; //分隔线旋转 ans=max(ans,cnt); //统计这一轮扫描的结果 } } return ans;}int main(){ while(~scanf("%d",&n)&&n) { rep(i,n) scanf("%d%d%d",&op[i].x,&op[i].y,&color[i]); printf("%d\n",solve()); }}

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

你可能感兴趣的文章