首页 > ACM题库 > HDU-杭电 > HDU 2945-Wires[解题报告]HOJ
2014
02-24

HDU 2945-Wires[解题报告]HOJ

Wires

问题描述 :

Engineer Bob is a strange man, and he makes his floor a simple polygon and installs various fantastic machines on his floor.

On Bob’s floor, there are n machines and n sockets. Each machine is fixed at a certain location and each socket is fixed at a certain position. Different machines and socket may be located at the same position.

Bob wants to connect one machine with exactly one socket by using wire and he hopes that the total length of the wires is minimal.
In addition, we assume that:
Bob’s floor can be described by m vertices in a 2-dimentional coordinate system. The m vertices are always given by clockwise or counter-clockwise. For simplicity, the edges of the polygon are always horizontal or vertical. For example, (0,0) (0,4) (4,4) (4,0) (2,0) (2,1) (3, 1) (3,2) (1,2) (1,0) describe the polygon which is shown in Figure 1, in which M1 and M2 are machines, S1 and S2 are sockets.

Wires can only be equipped within the polygon or on the edges of the polygon. Wires can be intercrossed.

Now please find out the minimal length of all the wires needed.

输入:

The input contains several cases. The first line of each case contains one integer m (1 ≤ m ≤ 100) indicating the number of vertices of the polygon. This is then followed by m lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith vertex of the polygon. And this is followed by one line, containing one integer n (1 ≤ n ≤ 16), indicating the number of machines (and also sockets).
This is followed by n lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith machine. And this is followed by n lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith socket. The input ends with m=0. It is guaranteed that the coordinates of all machines and sockets are always given within the polygon or on the edges of the polygon.

输出:

The input contains several cases. The first line of each case contains one integer m (1 ≤ m ≤ 100) indicating the number of vertices of the polygon. This is then followed by m lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith vertex of the polygon. And this is followed by one line, containing one integer n (1 ≤ n ≤ 16), indicating the number of machines (and also sockets).
This is followed by n lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith machine. And this is followed by n lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith socket. The input ends with m=0. It is guaranteed that the coordinates of all machines and sockets are always given within the polygon or on the edges of the polygon.

样例输入:

10
0 0
0 4
4 4
4 0
2 0
2 1
3 1
3 2
1 2
1 0
2
2 3
1 0
3 3
2 0
0

样例输出:

7.41

Hint
Hint For the sample input: M1 ->S1 distance = 1.000 M1 -> S2 distance = 3.828 M2 -> S1 distance = 4.236 M2 -> S2 distance = 6.414 Connecting machine M1 to socket S1 and machine M2 to socket S2, we will get the minimal length of wires 7.41.ting the minimal length of wires needed.

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;

const double eps=1e-5;
const double pi=acos(-1.0);
struct point_t
{
    double x, y;
    point_t() { }
    point_t(double tx, double ty) : x(tx), y(ty) { }
    point_t operator-(const point_t &r) const
    {
        return point_t(x - r.x, y - r.y);
    }
    point_t operator+(const point_t &r) const
    {
        return point_t(x + r.x, y + r.y);
    }
    point_t operator*(const double r) const
    {
        return point_t(x * r, y * r);
    }
    point_t operator/(const double r) const
    {
        return point_t(x / r, y / r);
    }
    void read()
    {
        scanf("%lf%lf", &x, &y);
    }
} p[4], tp[4];

int dblcmp(double x)
{
    return (x < -eps ? -1 : x > eps);
}

double dist(point_t p1, point_t p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

double cross(point_t p1, point_t p2)
{
    return p1.x * p2.y - p1.y * p2.x;
}

double dot(point_t p1, point_t p2)
{
    return p1.x * p2.x + p1.y * p2.y;
}

double angle(point_t p1, point_t p2, point_t p3)
{
    double d = dot(p2 - p1, p3 - p1) / dist(p1, p2) / dist(p1, p3);
    return acos(d);
}

point_t inter(point_t a, point_t b, point_t c, point_t d)
{
    point_t p1 = b - a, p2 = d - c;
    double a1 = p1.y, b1 = -p1.x, c1;
    double a2 = p2.y, b2 = -p2.x, c2;
    c1 = a1 * a.x + b1 * a.y;
    c2 = a2 * c.x + b2 * c.y;
    return point_t((c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1), (c1 * a2 - c2 * a1) / (b1 * a2 - b2 * a1));
}

point_t ver(point_t p1, point_t p2)
{
    point_t v = (p2 - p1) / 2 * sqrt(3.0);
    swap(v.x, v.y);
    v.x = -v.x;
    return v;
}

point_t fermat(point_t p1, point_t p2, point_t p3)
{
    if (angle(p1, p2, p3) > pi / 3 * 2) return p1;
    if (angle(p2, p1, p3) > pi / 3 * 2) return p2;
    if (angle(p3, p1, p2) > pi / 3 * 2) return p3;
    point_t v1 = ver(p1, p2);
    point_t m1 = (p1 + p2) / 2;
    if (dblcmp(cross(p3 - p1, p2 - p1)) * dblcmp(cross(v1 + m1 - p1, p2 - p1)) > 0) v1.x = -v1.x, v1.y = -v1.y;
    m1 = m1 + v1;
    point_t v2 = ver(p1, p3);
    point_t m2 = (p1 + p3) / 2;
    if (dblcmp(cross(p2 - p1, p3 - p1)) * dblcmp(cross(v2 + m2 - p1, p3 - p1)) > 0) v2.x = -v2.x, v2.y = -v2.y;
    m2 = m2 + v2;
    return inter(p3, m1, p2, m2);
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        for (int i=0; i<4;i++) p[i].read();
        double res = 1e10;
        for (int i=0; i<4; i++)
        {
            for (int j=i+1; j<4; j++)
            {
                int l=0, r=3;
                for (int k=0; k<4; k++)
                {
                    if (k==i||k==j)tp[l++]=p[k];
                    else tp[r--]=p[k];
                }
                point_t f1=tp[2];
                point_t f2=fermat(tp[0],tp[1],tp[2]);
                bool c=0;
                for (;;)
                {
                    point_t tf1, tf2;
                    if (c==0)
                    {
                        tf1=fermat(tp[2],tp[3],f2);
                        tf2=f2;
                    }
                    else
                    {
                        tf1=f1;
                        tf2=fermat(tp[0],tp[1],f1);
                    }
                    c^=1;
                    if(dblcmp(dist(tf1, f1)) == 0 && dblcmp(dist(tf2, f2)) == 0) break;
                    else f1 = tf1, f2 = tf2;
                }
                res = min(res, dist(f2, tp[0]) + dist(f2, tp[1]) + dist(f1, tp[2]) + dist(f1, tp[3]) + dist(f1, f2));
            }
        }
        printf("%.4lf\n",res);
    }
    return 0;
}

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  3. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?

  4. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }