code【泫若蓼蓝吧】

泫若蓼蓝吧关注：19贴子：1,926

3回复贴，共1页

code

#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX = 1010;
typedef struct COOR{
     int lx,ly,rx,ry;
     bool dir;                 // dir标记方向，true为南北，false为东西
}COOR;
COOR c[MAX];
int map[MAX][MAX];
int dis(int x1,int y1,int x2,int y2)
{
     return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}
int conDifDir(int i,int k) // 判断是否相连或者交叉
{
     if( c[k].lx >= c[i].lx && c[k].lx <= c[i].rx && c[i].ly >= c[k].ly && c[i].ly <= c[k].ry )
         return 1;
     return 0;
}

int conSamDir(int i,int k)
{
     if( c[i].dir == true )
     {
         if( c[i].ly != c[k].ly )
             return 0;
         if( c[i].rx >= c[k].lx && c[i].lx <= c[k].rx )
             return 1;
     }
     if( c[i].dir == false )
     {
         if( c[i].lx != c[k].lx )
             return 0;
         if( c[i].ly <= c[k].ry && c[i].ry >= c[k].ly )
             return 1;
     }
}
int minSamDis(int i,int k)
{
     if( c[i].dir == true )
     {
         if( c[i].lx <= c[k].rx && c[i].lx >= c[k].lx || c[i].rx >= c[k].lx && c[i].rx <= c[k].rx )
             return abs( c[i].ly - c[k].ly );
         return INT_MAX;
     }
     if( c[i].dir == false )
     {
     //     cout <<   i << ' ' << k << endl;cout << c[i].lx <<   ' ' << c[i].rx << ' '<< c[k].lx << ' ' << c[k].rx << endl;
         if( c[i].ly <= c[k].ry && c[i].ly >= c[k].ly || c[i].ry >= c[k].ly && c[i].ry <= c[k].ry )
             return abs( c[i].lx - c[k].lx );

送TA礼物

1楼2011-03-28 23:21回复

         return INT_MAX;
     }
}
int minDifDis(int i,int k)
{
     if( c[k].lx >= c[i].lx && c[k].lx <= c[i].rx )
         return min( abs(c[k].ly - c[i].ly),abs(c[k].ry - c[i].ly) );
     return INT_MAX;
}
int compute(int i,int k)
{
     int ans = 0;
     int a[5];
     if( c[i].dir == true && c[k].dir == false )
         ans = conDifDir(i,k);
     else
         if( c[i].dir == false && c[k].dir == true )
             ans = conDifDir(k,i);
         else
             ans = conSamDir(i,k);
     if( ans == 1 )
         return 0;
     a[0] = dis(c[i].lx,c[i].ly,c[k].lx,c[k].ly);
     a[1] = dis(c[i].lx,c[i].ly,c[k].rx,c[k].ry);
     a[2] = dis(c[i].rx,c[i].ry,c[k].lx,c[k].ly);
     a[3] = dis(c[i].rx,c[i].ry,c[k].rx,c[k].ry);
     if( c[i].dir == true && c[k].dir == false )
         a[4] = minDifDis(i,k);
     else
         if( c[i].dir == false && c[k].dir == true )
             a[4] = minDifDis(k,i);
         else
             a[4] = minSamDis(i,k);
     cout << a[4] << endl;
     if( a[4] != INT_MAX )
         a[4] *= a[4];
     int min = INT_MAX;
     for(int i=0; i<=4; i++)
         if( a[i] < min )
             min = a[i];
     return min;
}
int Dijkstra(int from,int to,int n)
{
     int dis[MAX];
     bool used[MAX];
     memset(used,false,sizeof(used));
     for(int i=0; i<n; i++)
         dis[i] = INT_MAX;
     int now = from;
     used[now] = 1;
     dis[from] = 0;
     for(int i=0; i<n; i++)
     {
         for(int k=0; k<n; k++)

2楼2011-03-28 23:21

         {
             int w = max( map[now][k],dis[now]);
                 if( w < dis[k] )
                     dis[k] = w;
         }
         int min = INT_MAX;
         for(int k=0; k<n; k++)
             if( !used[k] && dis[k] < min )
                 min = dis[now = k];
         used[now] = 1;
     }
     return dis[to];
}
int main()
{
     int n;
     int l;
     while( ~scanf("%d",&n) && n )
     {
         for(int i=0; i<n; i++)
         {
             scanf("%d%d%d",&c[i].lx,&c[i].ly,&l);
             if( l >= 0 )
             {
                 c[i].rx = c[i].lx;
                 c[i].ry = c[i].ly + l;
                 c[i].dir = false;
             }
             else
             {
                 c[i].rx = c[i].rx - l;
                 c[i].ry = c[i].ly;
                 c[i].dir = true;
             }
         }
     //     for(int i=0; i<n; i++)
     //         cout << c[i].lx << ' ' << c[i].ly <<' ' <<   c[i].rx << ' ' << c[i].ry << endl;
         for(int i=0; i<n; i++)
             for(int k=0; k<n; k++)
                 if( i != k )
                     map[i][k] = compute(i,k);
         for(int i=0; i<n; i++)
         {
             for(int k=0; k<n; k++)
                 cout << map[i][k] << ' ';
             cout << endl;
         }
         int ans = Dijkstra(1,2,n);
         cout << ans << endl;
     }
system("pause");
return 0;
}

3楼2011-03-28 23:21