huring
0%

51nod-1942-安装监控

Posted on Edited on In

题目：
现在要在办公室里面安装监控， 由于预算有限，现在只能安装一个摄像头，这个摄像头是可以360度旋转的。现在就要选择一个位置安装这个摄像头，使得它能够监控到办公室中的所有地方。办公室的边界以多边形给出，这个多边的所有边都是平行于座标轴的，并且不自交。

样例解释：

左边的图对应的是第一个样例，把摄像头安装在点的位置就可以监控到所有的地方了，右边的图对应第二个样例，这个办公室没有办法找到一个地方安装摄像头使得所有地方都被监控到，如果安装在点的位置，灰色的部分就不能被监控到了。

输入
单组测试数据。
第一行有一个整数n (4 <= n <= 100)，表示多边形的顶点数目。
接下来n行，每行出两个整数x 和 y（-100000<=x,y<=100000），表示多边形的顶点，以顺时针的方向给出。
所有的顶点都是不一样的。
输出
如果能够安装一个摄像头使得所有区域被监控到输出Yes，否则输出No。
输入样例
样例输入1
4
0 0
0 1
1 1
1 0

样例输入2
8
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0
输出样例
样例输出1
Yes
样例输出2
No
解法：
循环每条线段得到最终满足条件区域，最后判断区域是否为空即可
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<algorithm>
using namespace std;
const int inf = 99999999;
int main()
{
    int n;
    scanf("%d", &n);
    n--;
    int X,Y;
    scanf("%d%d", &X, &Y);
    int px = X, py = Y;
    int lx = -inf,rx = inf, ly = -inf, ry = inf;
    while(n--)
    {
        int x,y;
        scanf("%d%d", &x, &y);
        if(y < Y)
            rx= min(rx, X);
        if(y > Y)
            lx = max(lx, X);
        if(x > X)
            ry = min(ry, Y);
        if(x < X)
            ly = max(ly, Y);
        X = x; Y = y;
    }
    if(py < Y)
        rx= min(rx, X);
    if(py > Y)
        lx = max(lx, X);
    if(px > X)
        ry = min(ry, Y);
    if(px < X)
        ly = max(ly, Y);
    //printf("%d %d %d %d\n", lx, rx, ly, ry);
     if(ly > ry || lx > rx)
        printf("No");
     else
     {
         printf("Yes");
     }
     return 0;
}