首页 > ACM题库 > HDU-杭电 > HDU 3432-Wax-模拟-[解题报告]HOJ
2014
03-23

HDU 3432-Wax-模拟-[解题报告]HOJ

Wax

问题描述 :

You are a flooring contractor with bickering employees. You need to have these employees work together to wax the floor of some rooms, each with 1 door.

None of the workers want to work more than the others, and insist on working together so they can see if someone else is goofing off, so you must assign equal areas of each room to each employee. Each worker is assigned a contiguous portion of the room to wax. The portions assigned are separated by straight line segments that radiate out from the doorway to a wall in the room, so they can exit the room after the job is done.

输入:

The input is a series of problem definitions as follows:

WIDTH HEIGHT DOOR WORKERS

Each is a non-negative integer value less than or equal to 100, with at least 2 workers, and a positive WIDTH and HEIGHT. They specify the positions of the corners of the room: (0,0), (WIDTH,0), (WIDTH,HEIGHT), and (0,HEIGHT), as well as the location of the door: (DOOR,0), 0 < DOOR < WIDTH. Each problem definition is given on its own line.

The end of input is indicated by a list of 4 zeros:

0 0 0 0

输出:

The input is a series of problem definitions as follows:

WIDTH HEIGHT DOOR WORKERS

Each is a non-negative integer value less than or equal to 100, with at least 2 workers, and a positive WIDTH and HEIGHT. They specify the positions of the corners of the room: (0,0), (WIDTH,0), (WIDTH,HEIGHT), and (0,HEIGHT), as well as the location of the door: (DOOR,0), 0 < DOOR < WIDTH. Each problem definition is given on its own line.

The end of input is indicated by a list of 4 zeros:

0 0 0 0

样例输入:

3 5 2 4
10 10 5 2
10 10 5 4
0 0 0 0

样例输出:

2.500 5.000 1.000 5.000 0.000 3.750
5.000 10.000
10.000 10.000 5.000 10.000 0.000 10.000

#include<stdio.h>
int main()
{
    double W,H,D;
    int num,t;
    while(scanf("%lf%lf%lf%d",&W,&H,&D,&num)!=EOF)
    {
        t=0;
        double s=(W*H)/num;
        s*=2;
        double l,x;
        x=l=s/(W-D);
        while(x<=H)
        {
            t++;
            printf("%.3lf %.3lf",W,x);
            x+=l;
            if(t<num-1)
                printf(" ");
            else
            {
                printf("/n");
                goto loop;
            }
        }
        x-=l;
        x=W-(s-(H-x)*(W-D))/H;
        l=s/H;
        while(x>=0)
        {
            t++;
            printf("%.3lf %.3lf",x,H);
            x-=l;
            if(t<num-1)
                printf(" ");
            else
            {
                printf("/n");
                goto loop;
            }
        }
        x+=l;
        x=H-(s-(x*H))/D;
        l=s/D;
        while(x>0)
        {
            t++;
            printf("%.3lf %.3lf",0.0,x);
            x-=l;
            if(t<num-1)
                printf(" ");
            else
            {
                printf("/n");
                goto loop;
            }
        }
        loop :continue;
    }
    return 0;
}

参考:http://blog.csdn.net/snybzi/article/details/5734090


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  4. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。