专栏首页owentPOJ PKU 1474 Video Surveillance 解题报告

POJ PKU 1474 Video Surveillance 解题报告

题目链接:http://poj.org/problem?id=1474

写这题的目的是看完了zzy的论文,写了半平面交,验证一下正确性,结果发现我写的问题还是很多的。

题目大意是问能不能放一个摄像机,使得摄像机能看到整个多边形内部。

这题和1279和3130差不多,过了这题再去对付那两题就简单多了。

代码如下:

/**
 * 二维ACM计算几何模板
 * 注意变量类型更改和EPS
 * #include <cmath>
 * #include <cstdio>
 * By OWenT
 */


#include <cmath>
#include <cstdio>
#include <algorithm>

const double eps = 1e-8;
const double pi = std::acos(-1.0);
//点
class point
{
public:
    double x, y;
    point(){};
    point(double x, double y):x(x),y(y){};

    static int xmult(const point &ps, const point &pe, const point &po)
    {
        return (ps.x - po.x) * (pe.y - po.y) - (pe.x - po.x) * (ps.y - po.y);
    }
};

//两点表示的向量
class pVector
{
public:
    point s, e;//两点表示,起点[s],终点[e]

    pVector(){}
    pVector(const point &s, const point &e):s(s),e(e){}

    //向量与向量的叉乘,参数:向量[_Off]
    double operator *(const pVector &_Off) const
    {
        return (e.x - s.x) * (_Off.e.y - _Off.s.y) - (e.y - s.y) * (_Off.e.x - _Off.s.x);
    }

    //直线平行,参数:直线向量[_Off]
    bool parallel(const pVector &_Off) const
    {
        return std::fabs((*this) * _Off) < eps;
    }

    //两直线交点,参数:目标直线[_Off]
    point crossLPt(pVector _Off)
    {
        //注意先判断平行和重合
        point ret = s;
        double t = ((s.x - _Off.s.x) * (_Off.s.y - _Off.e.y) - (s.y - _Off.s.y) * (_Off.s.x - _Off.e.x))
                / ((s.x - e.x) * (_Off.s.y - _Off.e.y) - (s.y - e.y) * (_Off.s.x - _Off.e.x));
        ret.x += (e.x - s.x) * t;
        ret.y += (e.y - s.y) * t;
        return ret;
    }
};

class polygon
{
public:
    const static long maxpn = 2000;
    point pt[maxpn];//点(顺时针或逆时针)
    long n;//点的个数

    //-----------半平面交-------------
    //复杂度:O(nlog2(n))
    //#include <algorithm>
    //半平面计算极角函数[如果考虑效率可以用成员变量记录]
    static double hpc_pa(const pVector &_Off)
    {
        return atan2(_Off.e.y - _Off.s.y, _Off.e.x - _Off.s.x);
    }
    //半平面交排序函数[优先顺序: 1.极角 2.前面的直线在后面的左边]
    static bool hpc_cmp(const pVector &l, const pVector &r)
    {
        double lp = hpc_pa(l), rp = hpc_pa(r);
        if(fabs(lp - rp) > eps)
            return lp < rp;
        return point::xmult(l.s, r.e, r.s) < 0.0;
    }
    //用于计算的双端队列
    pVector dequeue[maxpn];
    //获取半平面交的多边形
    //参数:向量集合[l],向量数量[ln];(半平面方向在向量左边)
    polygon& halfPanelCross(pVector _Off[], int ln)
    {
        int i, tn;
        n = 0;
        std::sort(_Off, _Off + ln, hpc_cmp);
        //平面在向量左边的筛选
        for(i = tn = 1; i < ln; i ++)

            if(fabs(hpc_pa(_Off[i]) - hpc_pa(_Off[i - 1])) > eps)
                _Off[tn ++] = _Off[i];
        ln = tn;
        int bot = 0, top = 1;
        dequeue[0] = _Off[0];
        dequeue[1] = _Off[1];
        for(i = 2; i < ln; i ++)
        {
            if(dequeue[top].parallel(dequeue[top - 1]) ||
                dequeue[bot].parallel(dequeue[bot + 1]))
                return (*this);
            while(bot < top &&
                point::xmult(dequeue[top].crossLPt(dequeue[top - 1]), _Off[i].e, _Off[i].s) > eps)
                top --;
            while(bot < top &&
                point::xmult(dequeue[bot].crossLPt(dequeue[bot + 1]), _Off[i].e, _Off[i].s) > eps)
                bot ++;
            dequeue[++ top] = _Off[i];
        }

        while(bot < top &&
            point::xmult(dequeue[top].crossLPt(dequeue[top - 1]), dequeue[bot].e, dequeue[bot].s) > eps)
            top --;
        while(bot < top &&
            point::xmult(dequeue[bot].crossLPt(dequeue[bot + 1]), dequeue[top].e, dequeue[top].s) > eps)
            bot ++;
        //计算交点(注意不同直线形成的交点可能重合)
        if(top <= bot + 1)
            return (*this);
        for(i = bot; i < top; i ++)
            pt[n ++] = dequeue[i].crossLPt(dequeue[i + 1]);
        if(bot < top + 1)
            pt[n ++] = dequeue[bot].crossLPt(dequeue[top]);
        return (*this);
    }
};

pVector line[polygon::maxpn];
point pt[polygon::maxpn];
polygon ans;

int main()
{
    int n, i;
    int t = 1;
    //freopen("d:\\in.txt", "r", stdin);
    //freopen("d:\\myout.txt", "w", stdout);
    while(::scanf("%d", &n), n)
    {
        for(i = 0; i < n; i ++)
            ::scanf("%lf %lf", &pt[i].x, &pt[i].y);
        for(i = 0; i < n; i ++)
            line[i] = pVector(pt[(i + 1) % n], pt[i]);

        if(t > 1)
            puts("");
        ::printf("Floor #%d\n", t ++);
        ans.halfPanelCross(line, n);
        if(ans.n > 0)
            ::printf("Surveillance is possible.\n");
        else
            ::printf("Surveillance is impossible.\n");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

    从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

    haifeiWu
  • 知识体系解决迷茫的你

    最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

    桃翁
  • 中国互联网协会发布:《2018中国互联网发展报告》

    在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

    钱塘数据
  • ISUX Xcube智能一键生成H5

    腾讯ISUX
  • 不只是软件,在线也可以免费下载百度文库了。

    不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

    课代表
  • SQL中GROUP BY用法示例

    GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

    Awesome_Tang
  • 【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

    腾讯高校合作
  • 理工男图解零维到十维空间,烧脑已过度,受不了啦!

    让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

    钱塘数据
  • 【系统设置】CentOS 修改机器名

    ken.io
  • 考研英语-1-导学

    英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

    用户1335799

扫码关注云+社区

领取腾讯云代金券