poj 1556 The Doors 最短路 + 线段判交

代码有点猥琐。纪念下第一道几何

Source Code

Problem: 
1556  User: hehexiaobai 
Memory: 1092K  Time: 0MS 
Language: G
++  Result: Accepted 

Source Code 
#include
<iostream> // poj 1556
#include<cmath>
#include
<cstring>
using namespace std;
const int MAX = 205;
const double epsilon = 1e-10;
const double PI = acos(-1.0);

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

struct Point
{
    
double x, y;
    Point(){}
    Point(
double a, double b): x(a), y(b){}  

    Point 
operator + (Point b){
        
return Point(x + b.x, y + b.y);
    }

    Point 
operator - (Point b){
        
return Point(x - b.x, y - b.y);
    }

    
double operator * (Point b){
        
return x* b.y - y *b.x;
    }

    
bool operator == (Point b){
        
return (fabs(x - b.x)< epsilon) && (fabs(y - b.y) < epsilon);
    }
};

Point point[MAX];
double dis[MAX];
bool mp[MAX][MAX];
int nwalls, cntpoint; 

int direction(Point &p0, Point & p1, Point & p2)//判断 p0p2是从向量p1p0绕p0的旋转方向
{
    
double d = (p2 - p0) * (p1 - p0);
    
if(fabs(d) < epsilon) return 0;  //共线

    
if(d > 0.0return 1;  //顺时针
    
    
return -1;  //逆时针
}

bool inBox(Point &pi, Point & pj, Point &pk)
{
    
return min(pi.x , pj.x) <= pk.x && pk.x <= max(pi.x, pj.x) &&
           min(pi.y , pj.y) 
<= pk.y && pk.y <= max(pi.y, pj.y);
}

bool segmentsIntersect(Point &p1, Point & p2, Point & p3, Point & p4)
{
    
int d1 = direction(p3, p4, p1),
        d2 
= direction(p3, p4, p2),
        d3 
= direction(p1, p2, p3),
        d4 
= direction(p1, p2, p4);

    
if(d1 * d2 < 0  && d3 * d4 <0)
        
return true;
    
    
if( d1 == 0 && inBox(p3, p4, p1))
        
return true;

    
if( d2 == 0 && inBox(p3, p4, p2))
        
return true;
    
    
if( d3 == 0 && inBox(p1, p2, p3))
        
return true;

    
if( d4 ==0 && inBox(p1, p2, p4))
        
return true;
    
    
return false;
}

void Dijstra()
{
    
int i,j ;
    
double d[MAX][MAX] ;    
    memset(d, 
0sizeof d);
    
for( i = 0; i < cntpoint; i ++)
        
for(j = i + 1; j < cntpoint; j++)
        {
            d[i][j] 
= d[j][i] = sqrt((point[i].x - point[j].x) * (point[i].x - point[j].x)
                                    
+ (point[i].y - point[j].y)*(point[i].y - point[j].y));
        }

    
const double INF = 1e40;
    
bool visit[MAX] = {0};

    
for( i = 0; i < cntpoint; i ++)
        dis[i] 
= INF;
    dis[
0= 0.0

    
for( i = 0; i <cntpoint; i ++)
    {
        
int index = -1;
        
double min = INF;
        
for(j = 0; j < cntpoint; j ++)
            
if(!visit[j] && fabs(dis[j] - min) > epsilon && dis[j] < min)
            {
                index 
= j;
                min 
= dis[j];
            }
        
        
if(index == -1)return;
        visit[index] 
= true;

        
for( j = 0; j < cntpoint; j ++)
            
if(!visit[j] && mp[index][j] == true && dis[j] > dis[index] + d[index][j])
                dis[j] 
= dis[index] + d[index][j];

    }
}

int main()
{
    
    
int i , j;
    
while(cin >> nwalls)
    {
        
if( nwalls == -1)break;
        
        memset(point, 
0sizeof point);
        memset(mp, 
0sizeof (mp));
        memset(dis, 
0sizeof dis);

        point[
0].x = 0.0;
        point[
0].y = 5.0;
        
        
double x, y1, y2, y3, y4;
        cntpoint 
= 1;
        
for(i = 1;i <= nwalls; i ++)
        {
            cin 
>> x >> y1 >> y2 >> y3 >> y4;

            point[cntpoint].x 
= x;
            point[cntpoint].y 
= 0.0;
            cntpoint 
++;

            point[cntpoint].x 
= x;
            point[cntpoint].y 
= y1;
            cntpoint 
++;
            
            point[cntpoint].x 
= x;
            point[cntpoint].y 
= y2;
            cntpoint 
++;
            
            point[cntpoint].x 
= x;
            point[cntpoint].y 
= y3;
            cntpoint 
++;

            point[cntpoint].x 
= x;
            point[cntpoint].y 
= y4;
            cntpoint 
++;

            point[cntpoint].x 
= x;
            point[cntpoint].y 
= 10.0;
            cntpoint 
++;
        }

        point[cntpoint].x 
= 10.0;
        point[cntpoint].y 
= 5.0;
        cntpoint 
++;
        
        
int tempi, tempj;
        
        
for( i = 0;  i < cntpoint ; i ++)
            
for(j = i + 1; j < cntpoint; j ++)
            {
                tempi 
= i / 6;
                
if( i % 6 != 0) tempi += 1;
                
                tempj 
= j/6;
                
if( j % 6 != 0) tempj += 1;

                
if(tempi == tempj)continue;
                
if(point[i].y < epsilon || point[j].y < epsilon || 
                    
10.0 - point[i].y < epsilon || 10.0 - point[j].y < epsilon)
                        
continue;
                
                
bool flag = true;
                
forint k = tempi + 1; k < tempj; k ++)
                {
                    
int t = (k - 1* 6;
                
//    if(i == 0 && j == 9){ cout << flag << endl; cout << t << endl; }
                    if(segmentsIntersect(point[i],point[j],point[t + 1],point[t + 2]))flag = false;
                    
if(segmentsIntersect(point[i],point[j],point[t + 3],point[t + 4]))flag = false;
                    
if(segmentsIntersect(point[i],point[j],point[t + 5],point[t + 6]))flag = false;
                    
                }
                
if(flag == true)
                {
                    mp[i][j] 
= mp[j][i] = true;
                }
            }
        
    
//    for( i = 0; i < cntpoint; i ++,cout << endl)
    
//        for(j = 0; j < cntpoint; j ++)
    
//            cout << mp[i][j] <<" ";
        
    

        Dijstra();    
    
//    for(i = 0; i < cntpoint ; i ++)
    
//        cout << i <<' '<<dis[i] << endl;

        cout.precision(
2);
        cout 
<<fixed << dis[cntpoint - 1<< endl;
    }

    
return 0;
}
//0.0 0.0  1.0  1.0   1.0 0.0 1.0 1.0
//0.0 0.0  1.0  1.0   0.0 1.0 1.0  0.0
//0.0 0.0  1.0  1.0   1.0 0.0 1.0 0.9


posted on 2010-12-21 22:32 田兵 阅读(230) 评论(0)  编辑 收藏 引用 所属分类: 几何


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜