2825750_ac_15ms_156k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#define INF 2100000000

struct point
{
	double x, y;
};

point pt[100];
int pt_no;

struct segment
{
	point a, b;
};

segment seg[100];
int seg_no;

double map[100][100];
int n;

double max(double a,double b)
{
	return a > b ? a : b;
}

double min(double a,double b)
{
	return a < b ? a : b;
}

double multi(point p1,point p2,point p0)

{

    //求矢量[p0, p1], [p0, p2]的叉积

    //p0是顶点

    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);

    //若结果等于0，则这三点共线

    //若结果大于0，则p0p2在p0p1的逆时针方向

    //若结果小于0，则p0p2在p0p1的顺时针方向

}

bool isIntersected(point s1,point e1,point s2,point e2)
{

    if(

              (max(s1.x, e1.x) > min(s2.x, e2.x)) &&

              (max(s2.x, e2.x) > min(s1.x, e1.x)) &&

              (max(s1.y, e1.y) > min(s2.y, e2.y)) &&

              (max(s2.y, e2.y) > min(s1.y, e1.y)) &&

              (multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) &&

              (multi(s1, e2, s2) * multi(e2, e1, s2) >= 0)

              )  return true;

    

    return false;    

}


bool intersect(segment t)
{
	int i;

	for(i = 0; i < seg_no; i++)
	{
		if(seg[i].a.x>=max(t.a.x,t.b.x)||seg[i].a.x<=min(t.a.x,t.b.x))
			continue;
		if(isIntersected(t.a,t.b,seg[i].a,seg[i].b))
			return 1;
	}
	return 0;
}

double dis(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void dijkstra()
{
	int i, j, w;
	int s[101];
	double dist[101];

    for(i = 1; i <= pt_no; i++)
	{
        dist[i] = map[i][0];
        s[i] = 0;
    }
    s[0] = 1;dist[0] = 0;
    for(i = 0; i < pt_no-1; i++)
	{
        double min = INF;
        int u;
        for(j = 0; j < pt_no; j++)
		{
            if(!s[j]&&dist[j]<min)
			{
                u = j;
                min = dist[j];
            }
        }
        s[u] = 1;
        for(w = 0; w < pt_no; w++)
		{
            if(!s[w] &&  map[u][w] < INF && dist[w]>map[u][w]+dist[u])
			{
                dist[w] = map[u][w]+dist[u];
            }
        }
    }
	printf("%.2lf\n",dist[pt_no-1]);

}

int main()
{
	int i, j;
	point t;
	segment tmp;

	pt[0].x = 0;pt[0].y = 5;
	while(scanf("%d",&n)&&n!=-1)
	{
		pt_no = 1;seg_no = 0;
		for(i = 0; i < n; i++)
		{
			scanf("%lf",&t.x);
			for(j = 0; j < 4; j++)
			{
				scanf("%lf",&t.y);
				pt[pt_no++] = t;
				if(j==0)
				{
					seg[seg_no].a.x = t.x;
					seg[seg_no].a.y = 0;
					seg[seg_no++].b = t;
				}
				if(j==3)
				{
					seg[seg_no].a.x = t.x;
					seg[seg_no].a.y = 10;
					seg[seg_no++].b = t;
				}
				if(j==1)
					seg[seg_no].a = t;
				if(j==2)
					seg[seg_no++].b = t;
			}
		}
		pt[pt_no].x = 10;
		pt[pt_no++].y = 5;
		for(i = 0; i < pt_no; i++)
			for(j = 0; j < pt_no; j++)
				map[i][j] = map[j][i] = INF;
		for(i = 0; i < pt_no; i++)
			for(j = i+1; j < pt_no; j++)
			{
				if(pt[i].x==pt[j].x)
					continue;
				tmp.a = pt[i];
				tmp.b = pt[j];
				if(!intersect(tmp))
					map[i][j] = map[j][i] = dis(pt[i],pt[j]);
			}
		dijkstra();
	}
	return 0;
}