首页 > ACM题库 > HDU-杭电 > HDU 4688-Cut the Cake-计算几何-[解题报告]HOJ
2015
09-17

HDU 4688-Cut the Cake-计算几何-[解题报告]HOJ

Cut the Cake

问题描述 :

Mehmet is a nut cake seller. As the whole cake is too large and too heavy, a customer generally buys a specified part of it. The whole cake is a rectangle, while the specified part is a convex polygon region inside the rectangle. To get such specified part, Mehmet uses his sword to cut the cake. The only operation he can do is splitting a piece of cake into two parts by a straight cutting. As the cake is very solid, it cost as much as 1 unit energy to cut each length of cake. What’s the minimum energy Mehmet has to consume to satisfy the customer?
Boke and Tsukkomi

输入:

There are multiple test cases. Process to the End of File.

The first line of each test cases contains three integers 3≤N≤100, 0<W≤5000, 0<H≤5000, where W and H are the width and height of the nut cake. The next N lines are the vertices of the specified part in clockwise or counterclockwise order. Each line contains two integers 0<Xi<W and 0<Yi<H.

输出:

There are multiple test cases. Process to the End of File.

The first line of each test cases contains three integers 3≤N≤100, 0<W≤5000, 0<H≤5000, where W and H are the width and height of the nut cake. The next N lines are the vertices of the specified part in clockwise or counterclockwise order. Each line contains two integers 0<Xi<W and 0<Yi<H.

样例输入:

4 100 100
10 10
20 10
20 20
10 20
5 40 30
12 25
28 25
32 20
20 8
8 20

样例输出:

150.000000
109.494748

不讲题意了。

思路:

状态就是DP(i, j)表示i前面的切好了,j后面的切好了,求i到j这一节的答案。

DP思想就是这样。

计算几何真心不会写。计算几何是抄师傅的。

const int N = 222;
const double eps = 1e-10;

int vis[N][N];//这个状态求过
double res[N][N];
double to[N][2];//向左向右距离边缘的距离
double dd[N][N];//两线段相交,后一个线段距离交点的距离
bool lx[N][N];
int n;
double a, b;
double MAX;

struct Point {
    double x, y;

    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}

    Point operator -(const Point &p) const {
        return Point(x - p.x, y - p.y);
    }

    double xMul(const Point &p) const {
        return x * p.y - y * p.x;
    }
} p[N];

inline double dis(const Point &a, const Point &b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

struct Line {
    Point u, v;
    double w;

    Line() {}
    Line(const Point &_u, const Point &_v) : u(_u), v(_v) {
        w = dis(_u, _v);
    }
} line[N];

inline bool parallel(const Line &a, const Line &b) {
    return ZERO((a.v - a.u).xMul(b.v - b.u));
}

inline Point inter(const Line &a, const Line &b) {
    double s1 = (b.v - a.u).xMul(b.u - a.u), s2 = (b.u - a.v).xMul(b.v - a.v);
    return Point((a.u.x * s2 + a.v.x * s1) / (s2 + s1), (a.u.y * s2 + a.v.y * s1) / (s2 + s1));
}

void init(){
    int i, j;
    Point o, q[] = {Point(0, 0), Point(a, 0), Point(a, b), Point(0, b), Point(0, 0)};
    double l, r;

    for (i = 0; i < 2*n ; ++i) {
        for (j = 0; j < 2*n ; ++j) {
            if (j == i) continue;
            if (parallel(line[i], line[j])) {
                lx[i][j] = true; dd[i][j] = MAX;
            } else {
                o = inter(line[i], line[j]);
                l = dis(o, p[i]); r = dis(o, p[i + 1]);
                if (l < r) {
                    lx[i][j] = true; dd[i][j] = l;
                } else {
                    lx[i][j] = false; dd[i][j] = r;
                }
            }
        }
    }
    for (i = 0; i < 2*n; ++i) {
        to[i][0] = to[i][1] = MAX;
        for (j = 0; j < 4; ++j) {
            if (parallel(line[i], Line(q[j], q[j + 1]))) continue;
            o = inter(line[i], Line(q[j], q[j + 1]));
            l = dis(o, p[i]); r = dis(o, p[i + 1]);
            if (l < r) to[i][0] = min(to[i][0], l);
            else to[i][1] = min(to[i][1], r);
        }
            //cout<<i<<' '<<p[i].x<<' '<<p[i].y<<' '<<to[i][0]<<' '<<to[i][1]<<endl;
    }
}

double DP(int i, int j){
    if(i==j) return 0;
    if(vis[i][j]) return res[i][j];
    vis[i][j] = 1;
    double ans = MAX;
    for(int k=i; k<j; ++k){
        double ll = to[k][0];//点k到边界的距离
        double rr = to[k][1];//点k+1到边界的距离
        if(lx[k][i-1]) ll = min(ll, dd[k][i-1]);//如果k这头与i-1这条线段有交点
        else rr = min(rr, dd[k][i-1]);
        if (lx[k][j]) ll = min(ll, dd[k][j]);
        else rr = min(rr, dd[k][j]);

        ans = min(ans, DP(i, k) + DP(k+1, j) + ll + rr + line[k].w );
    }
    return res[i][j] = ans;
}

int main(){
    while(scanf("%d%lf%lf", &n, &a, &b)!=EOF){
        for (int i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
        for (int i = n; i <= 2 * n; ++i) p[i] = p[i - n];
        for (int i = 0; i < 2 * n; ++i) line[i] = Line(p[i], p[i + 1]);
        MAX = (a+b)*1000.0;
        init();

        memset(vis, 0, sizeof(vis));
        double ans = MAX;
        for (int i = 1; i <= n; ++i) {//枚举第一刀
            ans = min(ans, DP(i, i + n - 1) + to[i - 1][0] + to[i - 1][1] + line[i - 1].w);
        }
        printf("%lf\n", ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dslovemz/article/details/10129535