prolem ural 1369

Правка en1, от Los_Angelos_Laycurse, 2016-12-17 14:27:34

http://acm.timus.ru/problem.aspx?space=1&num=1369

today I have solved problem ural 1369. which spent me nearly two months and 600+ submits. now I'll share you approach of this problem:

first find voronoi diagram of this problem, and using sweepline algorithm to scan x cooridinates voronoi convex polygon

using set to record the point inside the polygon(sort by y cooridinates), for query, find the nearest y cooridinates scan the set from this nearest y points, if dist>min_dist+eps break..

I use this approach and WA on test 17, it is because there is precision error on voronoi points.

then I change sweepline the y cooridinates,and sort the set by x, it got WA on test 21(a different test)

so I combine this two approach together, and compare the two results,choose the minimum distance,finally get AC..

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Los_Angelos_Laycurse 2016-12-17 14:27:34 848 Initial revision (published)