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

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is to solve the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Spring13/Home\"><w:r><w:t>USC Spring 2013 ACM Contest</w:t></w:r></w:hyperlink><w:r><w:t> Problem E, Walking on Thin Ice.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>w=120</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>polycell={[0 10 0 90 50 50 100 90 100 10] [0 110 100 110 50 70]};</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> 35.6174</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The only USC competition solver(45 minutes):</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://contest.usc.edu/index.php/Spring13/Home?action=download&amp;upname=thinice.zhengcao.cpp.txt\"><w:r><w:t>Cao's C solution</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Theory:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Traveling Salesman Optimum Route. (Matlab one line while)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Create Interconnect Matrix</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Calculate Route/Distances between Good-Ice using Polygon to Polygon distance function.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Polygon to Polygon minimum distance uses minimum Point to Line Segment function.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Related Challenges:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>1)</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1446-minimum-distance-point-to-segment\"><w:r><w:t>Minimum Distance Point to Segment</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>2)</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1452-minimum-distance-between-two-n-sided-polygons\"><w:r><w:t>Minimum Distance between Polygons</w:t></w:r></w:hyperlink></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This Challenge is to solve the <a href = "http://contest.usc.edu/index.php/Spring13/Home">USC Spring 2013 ACM Contest</a> 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.Input:w=120polycell={[0 10 0 90 50 50 100 90 100 10] [0 110 100 110 50 70]};Output: 35.6174The only USC competition solver(45 minutes): <a href = "http://contest.usc.edu/index.php/Spring13/Home?action=download&upname=thinice.zhengcao.cpp.txt">Cao's C solution</a>Theory:Traveling Salesman Optimum Route. (Matlab one line while)Create Interconnect MatrixCalculate 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) <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1446-minimum-distance-point-to-segment">Minimum Distance Point to Segment</a>2) <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1452-minimum-distance-between-two-n-sided-polygons">Minimum Distance between Polygons</a>

This Challenge is to solve the <http://contest.usc.edu/index.php/Spring13/Home 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.

*Input:*

w=120

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): <http://contest.usc.edu/index.php/Spring13/Home?action=download&upname=thinice.zhengcao.cpp.txt Cao's C solution>

*Theory:*

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) <http://www.mathworks.com/matlabcentral/cody/problems/1446-minimum-distance-point-to-segment Minimum Distance Point to Segment>

2) <http://www.mathworks.com/matlabcentral/cody/problems/1452-minimum-distance-between-two-n-sided-polygons Minimum Distance between Polygons>

Solve

Solution Stats

8 Solutions
3 Solvers

Last Solution submitted on Jan 10, 2020

Last 200 Solutions

Problem Recent Solvers3

Problem Tags

2013 acm complex optimization traveling salesman usc

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

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

Solution Stats

Last 200 Solutions

Problem Recent Solvers3

Suggested Problems

More from this Author255

Problem Tags

Community Treasure Hunt

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

Solution Stats

Last 200 Solutions

Problem Recent Solvers3

Suggested Problems

More from this Author255

Problem Tags

Community Treasure Hunt

Players