关于Graham扫描法的两个问题

P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包

@[Skeleton_Huo](/user/324632) 第一个问题只是这个点一定在凸包上所以选这个点,只要是在凸包上的任意一个点跑graham都可以对,只是这个点好找 第二个问题可能就是有共线的情况,要再判断一个 a.y<b.y
by bamboo1030 @ 2023-08-23 22:07:57


@[bamboo123](/user/369181) 感谢,过了
by Skeleton_Huo @ 2023-08-24 09:11:06


@[bamboo123](/user/369181) 另外排序的第二关键字应该为到达基点的距离,而不是y
by Skeleton_Huo @ 2023-08-24 09:18:04


@[Skeleton_Huo](/user/324632) 本质差不多吧我的写法不太一样,我是直接把基点移成原点然后做凸包的
by bamboo1030 @ 2023-08-24 09:21:09


@[bamboo123](/user/369181) OK
by Skeleton_Huo @ 2023-08-24 09:27:24


1的话,x最大也可以其实 但是如果找x在中间的就会有一些奇妙的原因导致wa
by 萌田薰子 @ 2023-09-18 01:37:26


|