http://codeforces.com/contest/8/problem/D
If t2 is big enough for Bob to visit shop before go home, then ans=dist(cinema,shop,house)+t1
Otherwise we look for a point p such that
for Alan, d(cinema,p) + d(p,shop) + d(shop,house) <= d(cinema,shop,house)+t1
for Bob, d(cinema,p) + d(p,house) <= d(cinema,house)+t2
The trajectory for Alan is an ellipse and the same is true for Bob. So we need to find the intersection of two ellipses. This seems a bit difficult to program.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment