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

说下思路吧

Posted by KatrineYang at 2016-08-30 12:08:15 on Problem 1294
In Reply To:dp,几乎1A,atan函数为啥一定要用double,搞了一次CE,4776K 454ms(poj的编译器真是个吭) Posted by:KatrineYang at 2016-08-30 11:55:16
首先㞎原点平移到(洞,洞)。
然后,对其他的点进行有向角排序。注意原点不在头包上,所以排序以后相邻(最后一个和第一个也算相邻)的有向角之差一定小于派,但是对任意一个点,不可能其余点和它的角差都小于派(这个很有用)
然后枚举每一個起始点st,考虑以這個點开始逆时针方向走k個點时,构成的头包的面积。具體是:從起始点开始往後扫描并维护头包顶点。掃到新的顶点的时猴,對之前记录下的头包构成顶点进行二分,找出第一个这样的头包的边,它与原点到目标点的连线的交点在那個连线内面(平行或者负向相交显然都祘在外面)。如果在内面的不存在,那麽直接把新的目标點加入头包序列(这是边界情况一定要单独考慮!),否则,删除以上头包边的第二个顶点往后的琐有头包顶点,并把新的點加入头包顶点中(這個很容易实现,只需要记录当前头包的顶点個数,写入新值的时猴自動覆盖舊值)。面积可以由记录下来的从st到之前没删除的最後一個顶点l的面积,加上原点、l和新加入的點的三國形的面积锝到。
當有向角差哒到派以上的时猴就停止,之後的面积都置为INF,以保证不会更新到它们。
然後就只需要使用dp嘚到任意(i,j)区间分成b个框框的情况下面积的最小值,问题就解决了

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