首页 > ACM题库 > HDU-杭电 > HDU 1469 Video Surveillance-计算几何-[解题报告] C++
2013
12-11

HDU 1469 Video Surveillance-计算几何-[解题报告] C++

Video Surveillance

问题描述 :

A friend of yours has taken the job of security officer at the Star-Buy Company, a famous depart- ment store. One of his tasks is to install a video surveillance system to guarantee the security of the customers (and the security of the merchandise of course) on all of the store’s countless floors. As the company has only a limited budget, there will be only one camera on every floor. But these cameras may turn around to look in every direction.The first problem is to choose where to install the camera for every floor. The only requirement is that every part of the room must be visible from there. In the following figure the left floor can be completely surveyed from the position indicated by a dot, while for the right floor, there is no such position, the given position failing to see the lower left part of the floor.

Before trying to install the cameras, your friend first wants to know whether there is indeed a suitable position for them. He therefore asks you to write a program that, given a ground plan, de- termines whether there is a position from which the whole floor is visible. All floor ground plans form rectangular polygons, whose edges do not intersect each other and touch each other only at the corners.

输入:

The input contains several floor descriptions. Every description starts with the number n of vertices that bound the floor (4 <= n <= 100). The next n lines contain two integers each, the x and y coordinates for the n vertices, given in clockwise order. All vertices will be distinct and at corners of the polygon. Thus the edges alternate between horizontal and vertical.A zero value for n indicates the end of the input.

输出:

For every test case first output a line with the number of the floor, as shown in the sample output. Then print a line stating “Surveillance is possible.” if there exists a position from which the entire floor can be observed, or print “Surveillance is impossible.” if there is no such position.Print a blank line after each test case.

样例输入:

4
0 0
0 1
1 1
1 0
8
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0
0

样例输出:

Floor #1
Surveillance is possible.

Floor #2
Surveillance is impossible.

还是半平面交,各种模板各种套,注意点的顺序,所以就不多说了

但是,这题的数据还是要提一下的,POJ 的 discuss 里面有组
80+ 行的数据
,这组数据标程给出的是 possible ,但是这个多边形的核的面积是0,因为到最后,核只有一条边(也可以这样理解,一个矩形,长是大于 0 的,但是宽等于 0 ),也就是说,不能用面积来判断,否则,就

一直 WA 吧……

处理方法就是判断核的边数,看边数是否大于 0


代码:

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

const int N = 101;
const double eps = 1e-8;
const double pi = acos(-1.0);

struct cpoint {//C++构造函数,默认缺省值为(0,0)
    double x, y;
    cpoint(double xx = 0, double yy = 0): x(xx), y(yy) {};
};

int dcmp(double x) {//判断参数的符号,负数返回-1,0返回0,正数返回1
    if (x < -eps) return -1; 
	else return x > eps;
}

double xmult(cpoint p0, cpoint p1, cpoint p2) { // p0p1 与 p0p2 叉积
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

bool EqualPoint(cpoint a, cpoint b) {//两点相等
    return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

struct cvector {//向量
    cpoint s, e;
    double ang, d;
};

//atan (double x)弧度表示的反正切
//atan2(double x,double y)弧度表示的反正切,相当于atan(x/y)

void setline(double x1, double y1, double x2, double y2, cvector &v) {
    v.s.x = x1; v.s.y = y1;
    v.e.x = x2; v.e.y = y2;
    v.ang = atan2(y2 - y1, x2 - x1);
	//这里的 d 代表向量(直线)和坐标轴的截距,正数表示 原点 在该向量的左边
	//(这道题要求左半平面交),负号则表示 原点 在右边
    if (dcmp(x1 - x2))          // x1 > x2
		v.d = (x1 * y2 - x2 * y1) / fabs(x1 - x2);
    else v.d = (x1 * y2 - x2 * y1) / fabs(y1 - y2);
}

//判向量平行
bool parallel(const cvector &a, const cvector &b) {
    double u = (a.e.x - a.s.x) * (b.e.y - b.s.y) - (a.e.y - a.s.y) * (b.e.x - b.s.x);
    return dcmp(u) == 0;
}

//求两向量(直线)交点 (两向量不能平行或重合)
cpoint CrossPoint(const cvector &a, const cvector &b) {
    cpoint res;
    double u = xmult(a.s, a.e, b.s), v = xmult(a.e, a.s, b.e);
    res.x = (b.s.x * v + b.e.x * u) / (u + v);
    res.y = (b.s.y * v + b.e.y * u) / (u + v);
    return res;
}

//半平面交排序函数[优先顺序: 1.极角 2.前面的直线在后面的左边]
static bool VecCmp(const cvector &l, const cvector &r) {
    if (dcmp(l.ang - r.ang)) return l.ang < r.ang;
    return l.d < r.d;
}

cvector deq[N]; //用于计算的双端队列

void HalfPanelCross(cvector vec[],int n,cpoint cp[],int &m)
{
	int i,tn;
	sort(vec,vec+n,VecCmp);
	for(tn=i=1;i<n;i++)
	{
		if(dcmp(vec[i].ang-vec[i-1].ang) != 0)
			vec[tn++]=vec[i];
	}n=tn;
	int bot=0, top=1;
	deq[0]=vec[0], deq[1]=vec[1];
	for(i=2;i<tn;i++)
	{
		if(parallel(deq[top],deq[top-1]) || parallel(deq[bot],deq[bot+1]))return ;
		while(bot<top && dcmp(xmult(vec[i].s,vec[i].e,CrossPoint(deq[top],deq[top-1])))<0)
			top--;
		while(bot<top && dcmp(xmult(vec[i].s,vec[i].e,CrossPoint(deq[bot],deq[bot+1])))<0)
			bot++;
		deq[++top]=vec[i];
	}
	while(bot<top && dcmp(xmult(deq[bot].s,deq[bot].e,CrossPoint(deq[top],deq[top-1])))<0)
		top--;
	while(bot<top && dcmp(xmult(deq[top].s,deq[top].e,CrossPoint(deq[bot],deq[bot+1])))<0)
		bot++;

	if(top <= bot+1)return ;

	m=0;
	for(i=bot;i<top;i++)
		cp[m++]=CrossPoint(deq[i],deq[i+1]);
	if(bot<top+1)
		cp[m++]=CrossPoint(deq[bot],deq[top]);
	m=unique(cp,cp+m,EqualPoint)-cp;
}

double PolygonArea(cpoint p[], int n) {
    if (n < 3) return 0;
    double s = p[0].y * (p[n - 1].x - p[1].x);
    for (int i = 1; i < n; ++i)
        s += p[i].y * (p[i - 1].x - p[(i + 1) % n].x);
    return fabs(s / 2); // 顺时针方向s为负
}

int n,m;
cvector v[N];
cpoint cp[N];

int main()
{
	int i,j,time=1;
	cpoint p[N];
	while(scanf("%d",&n),n)
	{
		memset(cp,0,sizeof(cp));
		memset(v,0,sizeof(v));

		m=0;     //m是全局变量,注意,单纯在外部函数中初始化,有时候不靠谱

		for(i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		p[n]=p[0];

		for(j=0,i=n;i>0;i--)
			setline(p[i].x,p[i].y,p[i-1].x,p[i-1].y,v[j++]);
		n=j;

		HalfPanelCross(v,n,cp,m);//向量(直线)集合,长度;点集,长度

		printf("Floor #%d\n",time++);

		if(!m)printf("Surveillance is impossible.\n");
		else printf("Surveillance is possible.\n");
		puts("");
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/l04205613/article/details/6627531


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮