Description
是否能在房间中找到一个位置来安装摄像头，使摄像头能监控到房间的每个角落。在平面图上，房间的墙只有横和竖的，没有斜的。
Input
有多个testcase。每个testcase，第一行是一个整数n(4 <= n <= 100)，表示顶点数。接下来n行各有两个整数，是每个点的坐标，点按顺时针方向排列。
n等于0表示输入结束。
Output
能找到要求的点，输出"Surveillance is possible."
不能，输出"Surveillance is impossible."
Sample Input
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
Sample Output
Floor #1
Surveillance is possible.
Floor #2
Surveillance is impossible.
思路：
限制摄像头位置的，是房间的突出部分，如下图中的ABCD。图一和图二阴影部分表示了突出部分ABCD限制下，摄像头能放置的范围。
所以，如果房间的所有突出部分的限制范围有交集，那交集即可行的区域。
由于墙只有横和竖，只需要记录x和y方向可行的区间。
识别突出部分：沿顺时针方向遍历线段，线段连续右转时，该部分即突出部分。
代码：
|
#include <iostream>
#include <vector>
using namespace std;
struct Point
{
int x, y;
};
int n;
vector<Point> pointList;
vector<bool> lineList;
int xBegin, xEnd;
int yBegin, yEnd;
int main()
{
int tastcase = 0;
cin >> n;
while (n != 0)
{
tastcase++;
int i;
xBegin = xEnd = yBegin = yEnd = 0;
pointList.clear();
lineList.clear();
Point tempP;
for (i=0; i<n; i++)
{
cin >> tempP.x >> tempP.y;
pointList.push_back(tempP);
if (tempP.x < xBegin) xBegin = tempP.x;
if (tempP.x > xEnd) xEnd = tempP.x;
if (tempP.y < yBegin) yBegin = tempP.y;
if (tempP.y > yEnd) yEnd = tempP.y;
}
pointList.push_back(pointList[0]);
pointList.push_back(pointList[1]);
pointList.push_back(pointList[3]);
//求线段的转向
for (i=0; i<pointList.size()-2; i++)
{
Point p01;
p01.x = pointList[i+1].x - pointList[i].x;
p01.y = pointList[i+1].y - pointList[i].y;
Point p02;
p02.x = pointList[i+2].x - pointList[i].x;
p02.y = pointList[i+2].y - pointList[i].y;
int cross = p01.x * p02.y - p02.x * p01.y;
if (cross < 0)
{
lineList.push_back(true);
}
else
{
lineList.push_back(false);
}
}
for (i=0; i<lineList.size()-1; i++)
{
if (lineList[i] && lineList[i+1])//连续右转
{
if (pointList[i].x == pointList[i+1].x)//垂直与x轴
{
int begin = pointList[i].x;
int end = pointList[i+2].x;
if (begin > end)
{
int t = begin; begin = end; end = t;
}
if (begin > xBegin)
{
xBegin = begin;
}
if (end < xEnd)
{
xEnd = end;
}
}
else
{
int begin = pointList[i].y;
int end = pointList[i+2].y;
if (begin > end)
{
int t = begin; begin = end; end = t;
}
if (begin > yBegin)
{
yBegin = begin;
}
if (end < yEnd)
{
yEnd = end;
}
}
}
}
cout << "Floor #" << tastcase << endl;
if (xBegin <= xEnd && yBegin <= yEnd)
{
cout << "Surveillance is possible." << endl << endl;
}
else
{
cout << "Surveillance is impossible." << endl << endl;
}
cin >> n;
}
return 0;
}
|
