pku2318toys

作者在 2010-08-05 21:48:33 发布以下内容
题目:pku2318
代码:计算几何+二分(AC)
//计算几何(叉积) + 二分搜索
// n m x1 y1 x2 y2.
// (0 < n <= 5000) 0 < m <= 5000).
#include <iostream>
#include <cmath>
using namespace std;
#define infinity 1e20
#define EP 1e-10
const double PI = 2.0*asin(1.0);    //高精度求PI
struct point {double x,y;};         //
struct line{ point a,b;};      //线段
int ans[5005];  //用于保存各个区域所含点的个数
line seg[5005]; //用于保存各线段
//计算叉积
double multi(point p0,point p1,point p2)
{  
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
void searcharea(point p,int n)// 二分搜索
{
int first=0,end=n+1,mid;
while(end-first>1)//当两者相差为1时即找到了p点所在的区域
{
  mid=(first+end)/2;
  if(multi(seg[mid].a,seg[mid].b,p)>0)end=mid;
  else first=mid;
  // 叉积大于0时表示 p点在线段seg[mid]的左边
}
ans[first]++;//p点在此区域,该区域内所含的点数加1
}
int main(int argc, char *argv[])
{
    int n,m,cnt=0;
    int i,j,k;
    double x1,y1,x2,y2;
    double x,y;
    point p[5005];
    while(scanf("%d",&n)!=EOF&&n)
    {
     memset(ans,0,sizeof(ans));
     scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2);
     seg[0].a.x=x1;seg[0].a.y=y2;
     seg[0].b.x=x1;seg[0].b.y=y1;
     for(i=1;i<=n;i++)
     {
      scanf("%lf%lf",&x,&y);
      seg[i].a.x=y;seg[i].a.y=y2;
      seg[i].b.x=x;seg[i].b.y=y1;
     }
     seg[i].a.x=x2;seg[i].b.y=y2;
     seg[i].b.x=x2;seg[i].b.y=y1;
  for(i=0;i<m;i++)
  {
   scanf("%lf%lf",&p[i].x,&p[i].y);
   searcharea(p[i],n);
  }
  if(cnt)printf("\n");  cnt++;
  for(i=0;i<=n;i++)
    printf("%d: %d\n",i,ans[i]);
    }
    system("pause");
    return 0;
}
代码二:计算几何+枚举(TLE)
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define infinity 1e20
#define EP 1e-10
const double PI = 2.0*asin(1.0);    //高精度求PI
struct point {double x,y;};         //
struct line{ point a,b;};      //线段

double Angle2D(double x1, double y1, double x2, double y2)
{
   double dtheta,theta1,theta2;

   theta1 = atan2(y1,x1);
   theta2 = atan2(y2,x2);
   dtheta = theta2 - theta1;
   while (dtheta > PI)
      dtheta -= 2*PI;
   while (dtheta < -PI)
      dtheta += 2*PI;
   return(dtheta);
}
bool InsidePolygon(point *polygon,int n,point p)
{
   int i;
   double angle=0;
   point p1,p2;

   for (i=0;i<n;i++) {
      p1.x = polygon[i].x - p.x;
      p1.y = polygon[i].y - p.y;
      p2.x = polygon[(i+1)%n].x - p.x;
      p2.y = polygon[(i+1)%n].y - p.y;
      angle += Angle2D(p1.x,p1.y,p2.x,p2.y);
   }

   if (fabs(angle) < PI)
      return  false;
   else
      return  true;
}

//n m x1 y1 x2 y2.
// (0 < n <= 5000) 0 < m <= 5000).

int main(int argc, char *argv[])
{
    int n,m,ans,cnt=0;
    int i,j,k;
    double x1,y1,x2,y2;
    double x,y;
    line seg[5005];
    point p[5005],polygon[4];
    while(scanf("%d",&n)!=EOF&&n)
    {
        scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2);
        seg[0].a.x=x1;seg[0].a.y=y2;
        seg[0].b.x=x1;seg[0].b.y=y1;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf",&x,&y);
            seg[i].a.x=y;seg[i].a.y=y2;
            seg[i].b.x=x;seg[i].b.y=y1;
        }
        seg[i].a.x=x2;seg[i].b.y=y2;
        seg[i].b.x=x2;seg[i].b.y=y1;
        for(i=0;i<m;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        if(cnt)printf("\n");  cnt++;
        for(i=0;i<=n;i++)
        {
             polygon[0]=seg[i].a;polygon[1]=seg[i+1].a;
             polygon[2]=seg[i+1].b;polygon[3]=seg[i].b;
             ans=0;
             //cout<<polygon[0].x<<' '<<polygon[0].y<<' '<<polygon[1].x<<' '<<polygon[1].y<<endl;
            
//cout<<polygon[2].x<<' '<<polygon[2].y<<' '<<polygon[3].x<<' '<<polygon[3].y<<endl;
            
//system("pause");   //pinplg(4,polygon,p[j])
             for(j=0;j<m;j++)
                if(InsidePolygon(polygon,4,p[j]))ans++;
             printf("%d: %d\n",i,ans);
        }
    }
    //system("pause");
    return 0;
}

计算几何 | 阅读 802 次
文章评论,共0条
游客请输入验证码
最新评论