10691 - Subway
Posted: Sat Aug 28, 2004 3:06 pm
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:(
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:(