10691 - Subway

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

10691 - Subway

Post by sunhong »

I use dynamic programming to solve this problem
But got many WA~

My algorithm is below:
1.For every point on the plane, first calculate the distance from it to
the origin. If this distance < d,ignore this point,if not so, store this point.
2.Sort these points by their angle(from 0 to 2*PI).
3.For every point, calculate the range [a1,b1], when a line's angle in this range, the distance from the point to this line<=d. Store the angle a1 and
b1 in array ang[].
4. For every element in array ang[],calculate how many points it can "cover", as well as the identifier of these points.
5.Use dynamic programming to calculate the minimum number of line,
they can "cover" all points.

Who can tell me if my algorithm wrong or right, or give me some data
to test? Thanks.
Sorry for my poor English:(

Post Reply

Return to “Volume 106 (10600-10699)”