Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

pku 1127 Jack Straws

 

#include <iostream>
using namespace std;
#define min(a,b)(a<b?a:b)
#define max(a,b)(a>b?a:b)
const int maxn=15;
struct point{int x,y;};
struct line{point a,b;};
line straw[maxn];
bool link[maxn][maxn];
int n;
int multi(point p1,point p2,point p0){
    
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool across(line u,line v)
{
    
if( max(u.a.x,u.b.x)>=min(v.a.x,v.b.x)&&
        max(v.a.x,v.b.x)
>=min(u.a.x,u.b.x)&&
        max(u.a.y,u.b.y)
>=min(v.a.y,v.b.y)&&
        max(v.a.y,v.b.y)
>=min(u.a.y,u.b.y)&&
        (multi(v.a,u.b,u.a)
*multi(u.b,v.b,u.a)>=0)&&
        (multi(u.a,v.b,v.a)
*multi(v.b,u.b,v.a)>=0)    )
    
return 1;
    
else return 0;
}


void check()
{
    
int i,j,k;
    
for(k=1;k<=n;k++)
        
for(i=1;i<=n;i++)
            
if(link[i][k])
                
for(j=1;j<=n;j++)
                    
if(link[k][j]) link[i][j]=true;    
}


int main()
{
    
while(scanf("%d",&n)!=EOF&&n)
    
{
        
int i,j;
        
for(i=1;i<=n;i++)
        
{
            
int sx,sy,ex,ey;
            scanf(
"%d%d%d%d",&sx,&sy,&ex,&ey);
            straw[i].a.x
=sx;straw[i].a.y=sy;
            straw[i].b.x
=ex;straw[i].b.y=ey;
        }

        
for(i=1;i<=n;i++)
            
for(j=1;j<=n;j++)
                link[i][j]
=link[j][i]=across(straw[i],straw[j]);    
        check();
        
int cx,cy;
        
while(scanf("%d%d",&cx,&cy)!=EOF&&cx!=0&&cy!=0)
            
if(link[cx][cy]) 
                printf(
"CONNECTED\n");
            
else printf("NOT CONNECTED\n");
    }

    
return 0;
}

posted on 2009-09-05 22:36 Drolca 阅读(290) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理