Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
楼下说的不对,极限数据最多也就200多个点,当然指的是纯净凸包,这题只需要求纯净凸包可以证明,坐标是整数点且范围到lim的纯净凸包上的点数量在sqrt(lim)附近,画个图就可以看出来,可以让横坐标每次x = x + 1,纵坐标y = y + x + 1,这样算下来,总的点数接近 n*(n+1)/2 + n*(n+1)/2 + n = n^2 + 2n n^2 + 2n < lim => n ~ sqrt(lim),所以总点数也就在200多左右,n^2的旋转卡壳很快就能过,3方的危险,至于O(n)的,网上的代码基本都被discuss里提供的一些数据hack了 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator