POJ 2318 TOYS(点在多边形内判定)
http://poj.org/problem?id=2318
题意:
有一个平行于坐标轴的长矩形,被n块木板分成了n+1个包间.然后给你一些点的坐标,问你每个包间各包含了几个点?
分析:
直接求出每个包间的4个点坐标(按时针顺序),然后对于每个点,用点在多边形内的模板直接判定即可.
本题容易超时,可以用int替代double来计算加快速度.且判断点在多边形内可以直接判断4个叉积即可,因为每个多边形都是凸4边行.
AC代码:
用C++提交,G++提交超时.
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=1e-10;
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
return x<0?-1:1;
}
const int maxn=5000+10;
struct Point
{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double Dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
bool InSegment(Point P,Point A,Point B)
{
return dcmp(Cross(A-B,P-A))==0 && dcmp(Dot(A-P,B-P))<=0;
}
/*
//本题由于都是4边行,必须加快速度判断.
//如果直接用下面这个函数模板,将超时
bool IsPointInPolygon(Point p,Point *poly,int n)
{
int wn=0;
for(int i=0;i<n;++i)
{
if(InSegment(p, poly[(i+1)%n], poly[i]) ) return true;
int k=dcmp( Cross(poly[(i+1)%n]-poly[i], p-poly[i] ) );
int d1=dcmp( poly[i].y-p.y );
int d2=dcmp( poly[(i+1)%n].y-p.y );
if(k>0 && d1<=0 && d2>0) ++wn;
if(k<0 && d2<=0 && d1>0) --wn;
}
if(wn!=0) return true;
return false;
}
*/
bool IsPointInPolygon(Point p,Point *poly)
{
for(int i=0;i<4;++i)
if(dcmp (Cross(poly[(i+1)%4]-poly[i], p-poly[i]) )>0 ) return false;
return true;
}
Point p[maxn];//需要判断位置的所有点
Point up[maxn],down[maxn];//记录上一排的n+1个点,和下一排的n+1个点
Point poly[maxn][4];
int ans[maxn];//保存第i个隔间有几个点
int main()
{
int n,m;
double x1,y1,x2,y2;
bool first=true;
while(scanf("%d",&n)==1 && n)
{
if(!first) printf("\n");
first=false;
scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2);
up[0]=Point(x1,y1);
up[n+1]=Point(x2,y1);
down[0]=Point(x1,y2);
down[n+1]=Point(x2,y2);
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&x1,&x2);
up[i]=Point(x1,y1);
down[i]=Point(x2,y2);
}
for(int i=0;i<=n;++i)
{
poly[i][0]=up[i];
poly[i][1]=up[i+1];
poly[i][2]=down[i+1];
poly[i][3]=down[i];
}
memset(ans,0,sizeof(ans));
for(int i=1;i<=m;++i)
{
double x,y;
scanf("%lf%lf",&x,&y);
for(int j=0;j<=n;++j)
if(IsPointInPolygon(Point(x,y), poly[j] ))
{
ans[j]++;
break;
}
}
for(int i=0;i<=n;++i)
printf("%d: %d\n",i,ans[i]);
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ 最接近点对问题 ACM北大 using namespace std; struct Point { float x; float y; };
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2002-Squares 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
poj1379 给予平面内一个点集; 使用模拟退火求出一个点使该点到上述点集内任意一点最短距离最长。
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
我在poj共做了175题,暂时传上来看看
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码