首页 > 试题广场 >

凸多边形内点统计

[编程题]凸多边形内点统计
  • 热度指数：259 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
二维平面上给定一个凸多边形和若干点，小强想要查询有多少个点在凸多边形内部，在边上的点不算作内部）。
凸多边形由顺序的顶点序列构成，顶点以及要查询的点都在整数坐标上。
如由(1,0), (0,1), (-1,0), (0,-1)构成的四边形中，(0,0)点在内部，而(1,1)点在外部。


输入描述:
首先输入vn（n<=1e4），表示凸多边形的顶点个数；
接下来输入vn个顶点，每个顶点由两个整数构成，分别表示横纵坐标x、y（-1e4<=x,y<=1e4）；
然后输入pn（pn<=1e4），表示要查询数；
接下来输入pn个点，每个点由两个整数构成，分别表示横纵坐标x、y（-1e4<=x,y<=1e4）。


输出描述:
输出一个整数，表示在凸多边形内部的点数
示例1

输入

4 1 0 0 1 -1 0 0 -1
2 0 0 1 1

输出

1
算法知识视频讲解
添加回答
刘禅挥泪斩孔明头像 刘禅挥泪斩孔明
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为80.00%
用例:
66 10 0 10 1 10 2 10 3 9 4 9 5 8 5 8 6 7 7 6 8 5 8 5 9 4 9 3 10 2 10 1 10 0 10 -1 10 -2 10 -3 10 -3 9 -4 9 -5 9 -6 8 -7 8 -7 7 -8 6 -9 5 -9 4 -9 3 -10 3 -10 2 -10 1 -10 0 -10 -1 -10 -2 -10 -3 -9 -3 -9 -4 -9 -5 -8 -6 -7 -7 -7 -8 -6 -8 -5 -9 -4 -9 -3 -9 -3 -10 -2 -10 -1 -10 0 -10 1 -10 2 -10 3 -10 4 -9 5 -9 5 -8 6 -8 7 -7 8 -6 8 -5 9 -5 9 -4 10 -3 10 -2 10 -1
10000 9 6 8 2 -7 -2 10 -7 8 -4 6 6 4 1 3 -6 -4 8 0 -4 1 -4 -5 -5 8 3 -9 3 0 3 4 5 -3 -8 3 -8 6 10 -1 0 7 -1 -3 -2 9 -6 -8 -6 10 3 -9 -4 2 -4 -4 3 10 3 -9 -5 4 -8 1 9 -3 5 -3 -2 10 -4 6 3 8 -7 4 4 9 1 9 -4 10 -9 0 7 -7 5 8 -4 6 -9 4 3 -2 9 2 -2 -3 -1 2 -7 -1 9 -7 9 -5 -2 6 5 0 2 -2 7 1 7 -1 -4 2 2 -6 -6 7 -8 5 9 -2 7 4 -7 5 -6 3 10 -5 -1 6 7 -1 2 9 1 -9 7 2 2 3 2 -9 -6 7 9 4 4 -8 0 -2 8 5 4 4 -2 2 6 9 -2 1 -1 -2 2 2 5 6 3 10 4 8 -2 10 2 6 8 9 -7 10 1 -4 0 2 -9 -3 -8 -5 -3 4 4 4 2 7 -6 2 3 4 -1 6 9 7 8 -5 -3 -2 5 9 10 -9 -3 4 5 -1 -9 -6 -5 10 2 8 -1 -5 9 -3 -7 -4 -2 5 -8 3 -6 10 8 6 -3 -4 1 -2 0 -4 -6 9 3 -3 8 -3 1 10 -5 -4 7 9 -4 3 -1 6 -7 -1 2

这个测试用例有问题，可以注意到从第3个点开始的(10, 2), (10, 3), (9,4), (9,5), (8, 5)这段，先左拐，再右拐，再左拐，根本不是凸多边形，因为沿着凸多边形的点按顺序地走只会一直左拐或者右拐，不会变。
换用射线法才过了，能过应该是因为用例没有多边形上的点和要验证的点都很多的情况，否则射线法O(pn*vn)的复杂度会超时。如果是合法的凸多边形通过二分搜索，复杂度可以只有O(pn*log(vn))
编辑于 2020-04-29 21:58:21 回复(0)
提交观点

问题信息

C++工程师 深信服
来自：深信服校园招聘c/c ...
上传者：小小
难度：
1条回答 2161浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号