首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
51cthink1419专题
uvalive6468,51cthink1419 Strange Antennas (离散化)
题意: 在一个 n x n 的平面上,给定 m 个等腰直角三角形(各点均为整数),问该平面上被三角形覆盖奇数次的点有多少个。 思路: 由于 n 较大,不能模拟解决,故使用离散化思想。 考虑每一行有多少点被覆盖了奇数次,题目从二维转换成一维。 对于每一行,考虑每个三角形在此行覆盖的线段,记录下每条线段的左端点 l 、右端点 r 保存在同一个数组中。 排序后则容易知道第一个到第二个数、第三到第四个
阅读更多...