gougou1016
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
1016
Metal Cutting
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1185
20 2006-07-15 03:31:35 00:03.75 884K C++ glimpse
一道很有意思的题目。我得程序运行的比较慢，估计会有很多很多有意思的方法。我的方法比较麻烦，但是比较适合ZJUACM/ICPC集训队的同学快速 AC。
先讲一下我总体的思路：就是模拟所有的切割方法，然后每次需要切割的长度，找出最小的。
递归p步，第k步要做的事是：切割多边形，得到该次切割的长度L。如果 k == p ，返回L，否则，将新多边形求一遍凸包，用没有切割过的线依次递归切割新的多边形，得到所有切割方法中的最短的总长度ML，返回 L + ML。
这道题有两个比较麻烦的地方，一个是凸包，一个是一条线切割多边形。
求凸包的方法有很多了，随便一种都可以。
关键是如何求线切割多边形？很惭愧，我用的是狗狗模块里现成的函数。说一下polygon_cut的参数，第一参数是待切割的多边形的点数，第二个是待切多边形的点，第三个和第四个是切割线的两点坐标，最后一个参数叫side,module的注释是线在side侧切割多边形。
当初写的时候，被这个side搞得焦头烂额，再惭愧下，如果把当时郁闷的时间用来查书就好了。看来我学东西有时候真的不求甚解，这就是和狗狗的差距呀。
言归正传，我用了一个全局point变量记录了最后的多边形的中心（就是一开始读入得p个点的x,y的平均数）。每次调用polygon_cut的时候就把他当作side，因为这个点必定在最后的多边形内。
最后是如何计算切割线的长度？方法同样比较多吧，大约是找出新的多边形和切割线共线的点，然后#•￥•% ￥#•
这道题，虽然我最后AC了，但是因为用了不明白原理的moudle，有些遗憾吧，不知道以后有没有重写的机会了。
----
上面这个方法不太好，正确的做法是空间复杂度为O(2^n^)，时间复杂度为O(2^n^*n*n)的动态规划
用掩码来表示有哪些边已经切了，再枚举准备切那条边，那么可以算出这条边要切多长
实际上可以先O(n^2^)预处理出所有直线（射线）与线段的交点，这样很好写1016
Metal Cutting
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1185
20 2006-07-15 03:31:35 00:03.75 884K C++ glimpse
一道很有意思的题目。我得程序运行的比较慢，估计会有很多很多有意思的方法。我的方法比较麻烦，但是比较适合ZJUACM/ICPC集训队的同学快速 AC。
先讲一下我总体的思路：就是模拟所有的切割方法，然后每次需要切割的长度，找出最小的。
递归p步，第k步要做的事是：切割多边形，得到该次切割的长度L。如果 k == p ，返回L，否则，将新多边形求一遍凸包，用没有切割过的线依次递归切割新的多边形，得到所有切割方法中的最短的总长度ML，返回 L + ML。
这道题有两个比较麻烦的地方，一个是凸包，一个是一条线切割多边形。
求凸包的方法有很多了，随便一种都可以。
关键是如何求线切割多边形？很惭愧，我用的是狗狗模块里现成的函数。说一下polygon_cut的参数，第一参数是待切割的多边形的点数，第二个是待切多边形的点，第三个和第四个是切割线的两点坐标，最后一个参数叫side,module的注释是线在side侧切割多边形。
当初写的时候，被这个side搞得焦头烂额，再惭愧下，如果把当时郁闷的时间用来查书就好了。看来我学东西有时候真的不求甚解，这就是和狗狗的差距呀。
言归正传，我用了一个全局point变量记录了最后的多边形的中心（就是一开始读入得p个点的x,y的平均数）。每次调用polygon_cut的时候就把他当作side，因为这个点必定在最后的多边形内。
最后是如何计算切割线的长度？方法同样比较多吧，大约是找出新的多边形和切割线共线的点，然后#•￥•% ￥#•
这道题，虽然我最后AC了，但是因为用了不明白原理的moudle，有些遗憾吧，不知道以后有没有重写的机会了。
上面这个方法不太好，正确的做法是空间复杂度为O(2n)，时间复杂度为O(2n*n*n)的动态规划
用掩码来表示有哪些边已经切了，再枚举准备切那条边，那么可以算出这条边要切多长
实际上可以先O(n2)预处理出所有直线（射线）与线段的交点，这样很好写