Algorithm 版 (精华区)

发信人: xiong (阿拉斯加棕熊), 信区: Algorithm
标  题: 1081K-Points Within-ZJU
发信站: 哈工大紫丁香 (2002年10月13日21:01:44 星期天), 站内信件

#include "stdio.h"
#include "iostream.h"
int main(void)
{
 int n,m,crossnumber;
 int i,j,temp;
 int casenumber;
 int *verticex,*verticey;
 int pointx,pointy;
 double crossx;
 casenumber=1;
 while(true)
 {
  cin>>n;
  if((n!=0)&&(casenumber!=1))
   cout<<endl;
  if(n==0)
   return 0;
  else
  {
   cout<<"Problem "<<casenumber<<":"<<endl;
   casenumber++;
   cin>>m;
   verticex=new int[n];
   verticey=new int[n];
   for(i=0;i<n;i++)
   {
    cin>>verticex[i]>>verticey[i];
   }
   for(i=0;i<m;i++)
   {
    cin>>pointx>>pointy;
    for(j=0;j<n;j++)
    {
     if((pointx==verticex[j])&&(pointy==verticey[j]))
     {
      cout<<"Within"<<endl;
      goto end;
     }
    }
    crossnumber=0;
    for(j=0;j<n;j++)
    {
     if(j==n-1)
      temp=0;
     else
      temp=j+1;
     if(((verticey[j]>pointy)&&(verticey[temp]<pointy))||((verticey[j]<point
y)&&(verticey[temp]>pointy)))
     {
      //垂直穿越
      if(verticex[j]==verticex[temp])
      {
       if(verticex[j]==pointx)
       {
        cout<<"Within"<<endl;
        goto end;
       }
       else if(verticex[j]<pointx)
       {
        crossnumber++;
       }
      }
      else
      {
       crossx=(double)((verticex[temp]-verticex[j])*(pointy-verticey[j]))/(d
ouble)(verticey[temp]-verticey[j])+verticex[j];
       if(crossx==pointx)
       {
        cout<<"Within"<<endl;
        goto end;
       }
       else if(crossx<pointx)
       {
        crossnumber++;
       }
      }
     }
     //另外考虑直线穿过顶点的情况
     if((verticey[j]==pointy)&&(verticex[j]<pointx))
     {
      crossnumber++;
     }
    }
    if(crossnumber%2==0)
     cout<<"Outside"<<endl;
    else
     cout<<"Within"<<endl;
    //每一个点判断完毕
    end:;
   }
   delete []verticex;
   delete []verticey;
  }
 }
 return 0;
}
--

                    为了民族的尊严    为了祖国的明天

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.226.228]