首页 > ACM题库 > HDU-杭电 > HDU 3228-Island Explorer-最小生成树-[解题报告]HOJ
2014
03-09

HDU 3228-Island Explorer-最小生成树-[解题报告]HOJ

Island Explorer

问题描述 :

A group of explorers has found a solitary island. They land on the island and explore it along a straight line. They build a lot of campsites while they advance. So the campsites are laid on the line.Coincidently, another group of explorers land on the island at the same time. They also build several campsites along another straight line. Now the explorers meet at the island and they decide to connect all the campsites with telegraph line so that they can communicate with each other wherever they are.

Simply building segments that connect a campsite to another is quite easy, but the telegraph line is rare. So they decide to connect all the campsites with as less telegraph line as possible. Two campsites are connected if they are directly connected with telegraph line or they are both connected to another campsite.

输入:

There are multiple test cases.
The number of the test cases is in the first line of the input.For each test case, first line contains two integers N and M (0≤N, M≤10000), which N is the number of the campsites of the first group of explorers and M is the number of the campsites of the second group of explorers. And there exist at least one campsite.

The next two lines contain eight integers Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. Their absolute values are less than 1000. The integers are the coordinates of four points A, B, C and D. The exploring path of the first group is begin with the first point A and end with the second point B, and the path of the second group is from the third point C to the fourth point D. Every pair of points is distinct.

The last two lines of the test case contain N and M real numbers; they indicate the positions of the campsites. Suppose the i-th real number in the first line is t. It means the x-coordinate of the i-th campsite is Ax * t + Bx * (1-t), and the y-coordinate is Ay * t + By * (1-t). Equally, the campsite on the second straight line is C * t + D * (1-t). You can assume that there are at most four digits in the decimal part, and the numbers are always between 0 and 1.

输出:

There are multiple test cases.
The number of the test cases is in the first line of the input.For each test case, first line contains two integers N and M (0≤N, M≤10000), which N is the number of the campsites of the first group of explorers and M is the number of the campsites of the second group of explorers. And there exist at least one campsite.

The next two lines contain eight integers Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. Their absolute values are less than 1000. The integers are the coordinates of four points A, B, C and D. The exploring path of the first group is begin with the first point A and end with the second point B, and the path of the second group is from the third point C to the fourth point D. Every pair of points is distinct.

The last two lines of the test case contain N and M real numbers; they indicate the positions of the campsites. Suppose the i-th real number in the first line is t. It means the x-coordinate of the i-th campsite is Ax * t + Bx * (1-t), and the y-coordinate is Ay * t + By * (1-t). Equally, the campsite on the second straight line is C * t + D * (1-t). You can assume that there are at most four digits in the decimal part, and the numbers are always between 0 and 1.

样例输入:

1
4 4
0 0 10 10
0 10 10 0
0.1 0.3 0.6 0.8
0.1 0.3 0.6 0.8

样例输出:

Case #1: 19.638
Hint

The graph below shows the solution of the sample test.

Heroes Arrangement

两条直线 直线上有若干个点 求这些点的最小生成树

分别在另一条线上求一点的垂足(用向量) ,二分X坐标得到可能连接的点 然后连边
二分X坐标的时候注意直线的平行于Y轴的情况 此时要二分Y轴

#include<stdio.h>
#include<stdlib.h>
#include<cmath>
#include<algorithm>
#define eps 1e-6
#define N 10010
using namespace std;
struct Point
{
    double x,y;
    Point(){}
    Point(double a,double b):x(a),y(b){}
};
struct Line
{
    Point a,b;
    Line(){}
    Line(Point u,Point v):a(u),b(v){}
};
struct Info
{
    int n;
    Point p[N];
    Line l;
    Point fa;
};
Info a,b;
struct Node
{
    int u,v;
    double len;
    Node(){}
    Node(int u0,int v0,double len0):u(u0),v(v0),len(len0){}
}nod[8*N];
bool cccc(Node a,Node b)
{
    return a.len < b.len;
}
int nod_n;
int Sig(double a)
{
    return a<-eps?-1:a>eps;
}
Point Intersection(Line u,Line v)
{
    Point ret=u.a;
    double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/
             ((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
    ret.x+=(u.b.x-u.a.x)*t;
    ret.y+=(u.b.y-u.a.y)*t;
    return ret;
}
int cmp(Point a,Point b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
double Dis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int Find(double num,Point p[],int n,int ind)
{
    int left=0,right=n;
    if(ind==1)
    {
        while(left+1<right)
        {
            int mid=(left+right)>>1;
            if(Sig(num-p[mid].y)>=0)
                left=mid;
            else
                right=mid;
        }
    }
    else
    {
        while(left+1<right)
        {
            int mid=(left+right)>>1;
            if(Sig(num-p[mid].x)>=0)
                left=mid;
            else
                right=mid;
        }
    }
    return left;
}
Point operator +(Point a,Point b)
{
    Point tmp;
    tmp.x=a.x+b.x;
    tmp.y=a.y+b.y;
    return tmp;
}
void Init()
{
    double t;
    double ax,ay,bx,by,cx,cy,dx,dy;
    scanf("%d%d",&a.n,&b.n);
    scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
    scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
    for(int i=0;i<a.n;i++)
    {
        scanf("%lf",&t);
        a.p[i].x=ax*t+bx*(1-t);
        a.p[i].y=ay*t+by*(1-t);
    }

    for(int i=0;i<b.n;i++)
    {
        scanf("%lf",&t);
        b.p[i].x=cx*t+dx*(1-t);
        b.p[i].y=cy*t+dy*(1-t);
    }

    sort(a.p, a.p+a.n, cmp);
    sort(b.p, b.p+b.n, cmp);

    a.l=Line(Point(ax,ay),Point(bx,by));
    a.fa=Point(by-ay,ax-bx);

    b.l=Line(Point(cx,cy),Point(dx,dy));
    b.fa=Point(dy-cy,cx-dx);

    nod_n=0;
    for(int i=0;i<a.n;i++)//连边
    {
        Point tp=Intersection(b.l,Line(a.p[i],b.fa+a.p[i]));
        if(cx==dx)
        {
            double y=tp.y;
            if(Sig(y-b.p[0].y)<=0)
                    nod[nod_n++]=Node(i,a.n,Dis(a.p[i],b.p[0]));
            else if(Sig(y-b.p[b.n-1].y)>=0)
                nod[nod_n++]=Node(i,a.n+b.n-1,Dis(a.p[i],b.p[b.n-1]));
            else
            {
                int pos=Find(y,b.p,b.n-1,1);
                double d1=Dis(a.p[i],b.p[pos]);
                double d2=Dis(a.p[i],b.p[pos+1]);
                nod[nod_n++]=Node(i,a.n+pos,d1);
                nod[nod_n++]=Node(i,a.n+pos+1,d2);
            }
        }
        else
        {
            double x=tp.x;
            if(Sig(x-b.p[0].x)<=0)
                nod[nod_n++]=Node(i,a.n,Dis(a.p[i],b.p[0]));
            else if(Sig(x-b.p[b.n-1].x)>=0)
                nod[nod_n++]=Node(i,a.n+b.n-1,Dis(a.p[i],b.p[b.n-1]));
            else
            {
                int pos=Find(x,b.p,b.n-1,2);
                double d1=Dis(a.p[i],b.p[pos]);
                double d2=Dis(a.p[i],b.p[pos+1]);
                nod[nod_n++]=Node(i,a.n+pos,d1);
                nod[nod_n++]=Node(i,a.n+pos+1,d2);
            }
        }
    }

    for(int i=0;i<b.n;i++)//连边
    {
        Point tp=Intersection(a.l,Line(b.p[i],a.fa+b.p[i]));
        if(ax==bx)
        {
            double y=tp.y;
            if(Sig(y-a.p[0].y)<=0)
                nod[nod_n++]=Node(i+a.n,0,Dis(b.p[i],a.p[0]));
            else if(Sig(y-a.p[a.n-1].y)>=0)
                nod[nod_n++]=Node(i+a.n,a.n-1,Dis(b.p[i],a.p[a.n-1]));
            else
            {
                int pos=Find(y,a.p,a.n-1,1);
                double d1=Dis(b.p[i],a.p[pos]);
                double d2=Dis(b.p[i],a.p[pos+1]);
                nod[nod_n++]=Node(i+a.n,pos,d1);
                nod[nod_n++]=Node(i+a.n,pos+1,d2);
            }
        }
        else
        {
            double x=tp.x;
            if(Sig(x-a.p[0].x)<=0)
                nod[nod_n++]=Node(i+a.n,0,Dis(b.p[i],a.p[0]));
            else if(Sig(x-a.p[a.n-1].x)>=0)
                nod[nod_n++]=Node(i+a.n,a.n-1,Dis(b.p[i],a.p[a.n-1]));
            else
            {
                int pos=Find(x,a.p,a.n-1,2);
                double d1=Dis(b.p[i],a.p[pos]);
                double d2=Dis(b.p[i],a.p[pos+1]);
                nod[nod_n++]=Node(i+a.n,pos,d1);
                nod[nod_n++]=Node(i+a.n,pos+1,d2);
            }
        }
    }
    for(int i=0;i<a.n-1;i++)
        nod[nod_n++]=Node(i,i+1,Dis(a.p[i],a.p[i+1]));
    for(int i=0;i<b.n-1;i++)
        nod[nod_n++]=Node(i+a.n,i+a.n+1,Dis(b.p[i],b.p[i+1]));

}

int parent[20010];
int find(int x)
{
    if(parent[x] != x)
        parent[x]=find(parent[x]);
    return parent[x];
}
int main()
{
    int cas;
    scanf("%d",&cas);
    for(int cc=1;cc<=cas;cc++)
    {
        Init();
        sort(nod,nod+nod_n,cccc);
        int n=a.n+b.n;
        for(int i=0;i<n;i++)
            parent[i]=i;
        int tmp=n-1;
        double total=0;
        int x,y;
        int px,py;
        for(int i=0;i<nod_n && tmp;i++)
        {
            x=nod[i].u;
            y=nod[i].v;
            px=find(x);
            py=find(y);
            if(px == py)
                continue;
            total+=nod[i].len;
            tmp--;
            if(rand()&1)
                parent[px]=py;
            else
                parent[py]=px;
        }
        printf("Case #%d: %.3f\n",cc,total);
    }
    return 0;
}