网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P3316
2024-12-19
P3316 [SDOI2014] 里面还是外面 题解
实现有些傻瓜,喜提时空双最劣解。首先要判断一个点是否在多边形内,一个比较好的方法是从这个点向上引一条射线,若和奇数条边相交就在多边形内,否则在多边形外。二维信息,考虑用树套树维护。把多边形的每一条边都扔到它\(x\)坐标范围的线段树节点里,即线段树节点\((l,r)\)里面维护