首页 > 其他 > 详细

hdu 1086 线段相交

时间:2014-03-18 13:56:00      阅读:461      评论:0      收藏:0      [点我收藏+]

这个题目就是基本的线段相交水题。

并且重复点竟然算2个,哪没办法了,水过,线段相交,跨立实验。

如何判断两条线段是否相交
判断两条线段是否相交 


(1) 快速排斥试验
  设以线段 P1P2 为对角线的矩形为 R , 设以线段 Q1Q2 为对角线的矩形为 T ,如果 R 和 T 
不相交,显然两线段不会相交。
(2) 跨立试验
  如果两线段相交,则两线段必然相互跨立对方。若 P1P2 跨立 Q1Q2 ,则矢量 ( P1 - Q1 ) 和
      ( P2 - Q1 ) 位于矢量 ( Q2 - Q1 ) 的两侧,
      即 ( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0 。
       上式可改写成 ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0 。
      当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时,说明 ( P1 - Q1 ) 和 ( Q2 - Q1 ) 共线,
      但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2 上;
      同理, ( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2 上。
     所以判断 P1P2 跨立 Q1Q2 的依据是: 
      ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0 。
      同理判断 Q1Q2 跨立 P1P2 的依据是:
      ( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0 。



代码如下:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const double eps=1e-10;
const int maxn=500;
struct point{
    double x,y;
};
point p[maxn],b[maxn];
bool ans[maxn];
double min(double a,double b) {return a < b ? a : b; }
double max(double a,double b) {return a > b ? a : b; }
bool inter(point a, point b, point c, point d){
    if( min(a.x, b.x) > max(c.x, d.x) ||
        min(a.y, b.y) > max(c.y, d.y) ||
        min(c.x, d.x) > max(a.x, b.x) ||
        min(c.y, d.y) > max(a.y, b.y) )
    return 0;
    double h, i, j, k;
    h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);//叉积
    i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);
    j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);
    k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);
    return h * i <= eps && j * k <= eps;
}
int main()
{
	int n;
	while(scanf("%d",&n),n){
		int i,j;
		for(i=0;i<n;i++){
			scanf("%lf %lf",&p[i].x,&p[i].y);
			scanf("%lf %lf",&b[i].x,&b[i].y);
		}
		int ans=0;
		for(i=0;i<n;i++)
			for(j=i+1;j<n;j++){
				if(inter(p[i],b[i],p[j],b[j])) ans++;
			}
		printf("%d\n",ans);
	}
	return 0;
}


hdu 1086 线段相交,布布扣,bubuko.com

hdu 1086 线段相交

原文:http://blog.csdn.net/cnh294141800/article/details/21449775

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!