Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1106 Transmitters---计算几何

Posted on 2009-09-17 20:36 Uriel 阅读(336) 评论(0)  编辑 收藏 引用 所属分类: POJ计算几何
最近一直在搞计算几何。。不过不是钻研。。而是临时抱佛脚应付比赛。。。- -||

判断给定圆心,半径的半圆最多覆盖多少点。。
叉积应用---叉积正负判断夹角是否180度以内。。
/*Problem: 1106  User: Uriel 
   Memory: 176K  Time: 0MS 
   Language: C++  Result: Accepted
*/

 
#include
<math.h>
#include
<stdio.h>
#include
<stdlib.h>
#define MAXN 1001

typedef 
struct point{
    
int x,y;
}
;

point P[MAXN],a,t;
int MAX;
double r;

int cross_product(point a,point c,point b)
{
    
return (a.x-b.x)*(c.y-b.y)-(c.x-b.x)*(a.y-b.y);
}


int In_Circle(point a,point b,double r)
{
    
if((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)<=r*r)
    
{
        
return 1;
    }

    
return 0;
}


int main()
{
    
int i,j,k,n;
    
while(scanf("%d %d %lf",&a.x,&a.y,&r)!=EOF)
    
{
        
if(r<0)break;
        scanf(
"%d",&n);
        k
=0;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%d %d",&t.x,&t.y);
            
if(In_Circle(a,t,r))
            
{
                P[
++k].x=t.x;
                P[k].y
=t.y;
            }

        }

        MAX
=0;
        
for(i=1;i<=k;i++)
        
{
            
int temp=0;
            
for(j=1;j<=k;j++)
            
{
                
if(cross_product(P[i],a,P[j])<=0)
                
{
                    temp
++;
                }

            }

            
if(2*temp<k)                //看Discuss才想到的 
            {
                temp
=k-temp;
            }

            
if(temp>MAX)MAX=temp;
        }

        printf(
"%d\n",MAX);
    }

    system(
"PAUSE");
    
return 0;
}

                
        

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理