作者在 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;
}
// 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;
}
#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;
}