POJ 2318 TOYS（计算几何）

题目大意：有一个矩形盒子，盒子里会有一些木块线段，并且这些线段是按照顺序给出的，有n条线段，把盒子分层了n+1个区域,然后有m个玩具，这m个玩具的坐标是已知的，问最后每个区域有多少个玩具

解题思路：因为线段是有序给出，所以不用排序，判断某个点在哪个区域，采用二分法，将某个点和线段的叉积来判断这个点是在线的左边或者右边，根据这个来二分找出区域

代码和思路参考与此链接：http://blog.csdn.net/wangjian8006

这也算我入门计算几何的第一道题了，首先看了一些有关资料，了解到叉积的重要性！！有2点，p1，p2构成一条线段L，L左边有一点p3，右边有一点p4，则（p1-p2）x（p3-p1）>0，（p1-p2）x（p4-p1）<0。

也就是说在L左边的点叉积>0，右边的<0。

剩下的就是二分找答案了，在记录到数组中，最后输出。

#include <iostream>

using namespace std;

#define _MAXL_ 5010

typedef struct{

	int x, y;

}POINT;

typedef struct{

	POINT first,second;

}LINE;

class CBox{

private:

	int nTop,nLeft,nRight,nButtom;

	int nCountLine;						//记录盒子里有多少条线

	LINE *pLine;						//记录线的信息

	int *pRange;						//记录区间中的玩具有多少个

	int Multi(POINT p1,POINT p2,POINT p0);			//叉积计算

public:

	CBox();

	virtual ~CBox();

	void SetBorder(int top,int left,int right,int buttom);		//设置盒子矩形坐标

	void AddLine(int first,int second);							//在盒子中增加一条线

	int GetRange(int val);								//得到某个区间中的玩具个数

	void SetToy(POINT toy);							//在盒子里放一个玩具

};

CBox::CBox(){

	nCountLine = 0;

	pLine = new LINE[_MAXL_];

	pRange = new int[_MAXL_];

	memset(pRange,0,sizeof(pRange)*_MAXL_);

}

CBox::~CBox(){

	delete []pLine;

	delete []pRange;

}

void CBox::SetBorder(int top,int left,int right,int buttom){

	nTop = top;

	nLeft = left;

	nRight = right;

	nButtom = buttom;

}

void CBox::AddLine(int topx,int buttomx){

	pLine[nCountLine].first.x = topx;

	pLine[nCountLine].first.y = nTop;

	pLine[nCountLine].second.x = buttomx;

	pLine[nCountLine].second.y = nButtom;

	nCountLine++;

}

int CBox::GetRange(int val){

	return pRange[val];

}

int CBox::Multi(POINT p1,POINT p2,POINT p0){

	 return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);

}

void CBox::SetToy(POINT toy){			//利用二分查找，查找出该点在哪个区间

	int l, r, mid;

	l=0,r=nCountLine-1;

	while (l < r){

		mid = (l+r)>>1;

		if (Multi(toy, pLine[mid].first, pLine[mid].second) > 0) l = mid + 1;

		else r = mid;

	}

	if (Multi(toy, pLine[l].first, pLine[l].second) < 0) pRange[l]++;

	else pRange[l+1]++;

}

int main(){

	int i,fx,lx;

	POINT a,b;

	int n,m;

	while(cin>>n && n){

		cin>>m>>a.x>>a.y>>b.x>>b.y;

		CBox box;

		box.SetBorder(a.y,a.x,b.x,b.y);

		for(i = 0;i < n;i++){

			cin>>fx>>lx;

			box.AddLine(fx,lx);

		}

		for(i = 0;i < m;i++){

			cin>>a.x>>a.y;

			box.SetToy(a);

		}

		for(i = 0;i <= n;i++){

			cout<<i<<": "<<box.GetRange(i)<<endl;

		}

		cout<<endl;

	}

	return 0;

}

巴特西

POJ 2318 TOYS（计算几何）

最新文章

热门文章