【计算几何】codeforces上面的一点简简单单的计算几何入门题

发布时间 2023-10-05 22:52:26作者: 木易meow

开篇碎碎念

我真的好喜欢开篇碎碎念啊(可恶真的是太话痨啦)最近有在cf上面写写题,唔不过还没上百题,过两天就可以写百题纪念啦,也还没上青,陌陌菜菜,陌陌在努力变强捏。

cf1850G The Morning Star

  • tag: 用map进行维护,斜率与坐标的关系
  • 题目链接:G. The Morning Star
  • 题意:找到一个点,使另一个点和它在四个基本方向或者斜向。问有多少种方法。
  • KEY:在45°斜向意味着x+y相等或者y-x相等。
  • 思路:四个map分别记录x坐标,y坐标,x+y 以及 x-y。循环遍历x坐标相同个数+y坐标相同个数+ x+y的和相同+ y-x的差相同的和(记得减去它本身哦)
  • waring:十年OI一场空,不开long long见祖宗

cf1307B Cow and Friend

  • tag:计算几何 贪心 1300
  • 题目链接:B. Cow and Friend
  • 题意:一次可以在二维空间内移动 ai 的距离,需要从(0,0)移动到(x,0),问最小移动次数
  • 贪心策略:1.尽可能的跳比较远的距离 2.当能直接跳到的时候直接跳

cf1648A Weird Sum

  • tag: 组合数学;计算几何;矩阵;排序算法;数学
  • 题目链接:A. Weird Sum
  • 思路:分别关注颜色相同的横坐标与纵坐标,分别计算距离,再相加。vector记录。