Problem 1457. USC Spring 2013 ACM: Walking on Thin Ice

This Challenge is to solve the USC Spring 2013 ACM Contest Problem E, Walking on Thin Ice.

The Rooster is crossing to the other side of the frozen river. Minimize his distance traveled on thin ice given a river width (w) and polygons(polycell) that denote non-thin ice regions. Start anywhere on the x-axis(y=0) and finish by reaching y=w.



polycell={[0 10 0 90 50 50 100 90 100 10] [0 110 100 110 50 70]};

Output: 35.6174

The only USC competition solver(45 minutes): Cao's C solution


Traveling Salesman Optimum Route. (Matlab one line while)

Create Interconnect Matrix

Calculate Route/Distances between Good-Ice using Polygon to Polygon distance function.

Polygon to Polygon minimum distance uses minimum Point to Line Segment function.

Related Challenges:

1) Minimum Distance Point to Segment

2) Minimum Distance between Polygons

Solution Stats

100.0% Correct | 0.0% Incorrect
Last solution submitted on Oct 07, 2014
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

MATLAB Academy

New to MATLAB?

Learn MATLAB today!

Join the 15-year community celebration.

Play games and win prizes!

Learn more