注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 3304 Segments 直线 线段求交  

2011-04-19 11:06:39|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
在二维空间上,给定一组线段,能否存在这样的一条直线,使所有线段在这条直线的投影会在一个点上。
如果沿着这个投影点做直线的垂线,那么这条垂线必会与所有的线段相交。那么本题就转换为能否找到一条直线与所有的线段相交。
想找这样的直线,就要去离散化的枚举,本题怎样有效的枚举是关键。
首先假设有一条直线与所有的线段相交,慢慢平移这条直线,使它恰好在某条线段L1的端点上。当然这个时候直线还是与所有的线段相交。
然后让直线在这个端点上慢慢旋转,使到直线又经过线段L2的端点。L2和L1要满足不是同一条线段,就算相同,你仍可以继续旋转,总会让直线找到L2,且不与L1同一样的线段。
这样只要枚举两条线段的端点做直线,判断其它的线段是否与这条直线相交即可。枚举过程中要注意所选的两条线段的端点有可能会在同一个端点上。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define eps 1e-10
int n;
struct point
{
        double x;
        double y;
};
struct line
{
        point a,b;
}p[105];
double xmult(point p1,point p2,point p0)
{
        return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dis(point p1,point p2)
{
        return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool judge(int i,int j,point p1,point p2)
{
     int k;
     for(k=0;k<n;k++)
     {
          if(k==i||k==j)
               continue;
          if(xmult(p1,p[k].a,p2)*xmult(p1,p[k].b,p2)>eps||dis(p1,p2)<eps)
               return false;
     }
     return true;
}
int main()
{
        int cas,i,j;
        bool flag;
        scanf("%d",&cas);
        while(cas--)
        {
                scanf("%d",&n);
                for(i=0;i<n;i++)
                        scanf("%lf%lf%lf%lf",&p[i].a.x,&p[i].a.y,&p[i].b.x,&p[i].b.y);
                flag=true;
                for(i=0;i<n-1;i++)
                {
                        for(j=i+1;j<n;j++)
                        {
                             flag=false;
                             if(judge(i,j,p[i].a,p[j].a)||judge(i,j,p[i].a,p[j].b)||judge(i,j,p[i].b,p[j].a)||judge(i,j,p[i].b,p[j].b))
                             flag=true;
                             if(flag)
                                  break;
                        }
                        if(flag)
                             break;
                }
                if(flag)
                        printf("Yes!\n");
                else
                        printf("No!\n");
        }
        system("pause");
        return 0;
}
  评论这张
 
阅读(187)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018