这是本文档旧的修订版!
upsolved by
solved by
upsolved by
solved by
upsolved by
solved by
upsolved by
solved by 2sozx
给定一个第一象限简单多边形,问一条从原点出发的直线最多将多边形分成多少块。$n\le10^5$
首先忽略掉三点共线的点,这样的点是没有意义的,之后对剩余的点进行极角排序,让直线逆时针扫这些点,将这些点分成四种情况。
upsolved by
upsolved by
0min:开局分题
10min:MJX发现C是签到冲C
33min:MJX WA,CSK冲G
46min:CSK AC,ZYF冲A
55min:ZYF AC A,MJX继续冲C
83min:MJX WA2,换CSK写C,MJX ZYF看J
167min:J WA3,CSK冲I
186min:CSK AC I,ZYF继续看J,MJX看H,CSK 看F
230min:CSK WA
232min:MJX AC H,继续看J
285min:CSK AC F,一起看J
295min:CSK想到了正解冲J
till end :CSK没写完,由于inque多开了几分钟