Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

楼下说的不对,极限数据最多也就200多个点,当然指的是纯净凸包,这题只需要求纯净凸包

Posted by TCgogogo at 2016-10-03 13:02:54 on Problem 2079
可以证明,坐标是整数点且范围到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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator