Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

两线段相交的模板(包含端点)

Posted by 421 at 2009-04-28 19:05:27 on Problem 1410
In Reply To:说说几种常见的错误.... Posted by:hutu_2000 at 2009-04-21 10:28:57
我自已用简单方法做了N久,WA N次,思路是这样的:先求交点,然后再求交点到两端点的距离之和是否等于两端点距离,但一直是WA,前几种容易错了情况我也考虑了,不知错在那里???,望大牛过来看看
double dis(double x,double y,double tx,double ty)
{
	return sqrt((tx-x)*(tx-x)+(ty-y)*(ty-y));
}
bool power(int x1,int y1,int x2,int y2,int x,int y,int tx,int ty)
{
	int a1=y2-y1,b1=x1-x2,c1=x1*(y2-y1)-y1*(x2-x1);
	int a2=ty-y,b2=x-tx,c2=x*(ty-y)-y*(tx-x);
	if(a1*b2==a2*b1)
	{
		if(c1*b2==b1*c2)
			return 1;
		else
			return 0;
	}
	double ex=(c1*b2-b1*c2)/double(a1*b2-a2*b1);
	double ey=(a1*c2-a2*c1)/double(a1*b2-a2*b1);
	if(dis(x1,y1,x2,y2)==dis(x1,y1,ex,ey)+dis(x2,y2,ex,ey)&&dis(x,y,tx,ty)==dis(x,y,ex,ey)+dis(tx,ty,ex,ey))
		return 1;
	else
		return 0;
}

这是后面一次AC的线段相交的模板
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
//计算cross product (P1-P0)x(P2-P0)
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);
}
//判三点共线
int dots_inline(point p1,point p2,point p3){
	return zero(xmult(p1,p2,p3));
}

//判点是否在线段上,包括端点
int dot_online_in(point p,point l1,point l2){
	return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
}

//判两点在线段同侧,点在线段上返回0

int same_side(point p1,point p2,point l1,point l2){
	return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}

//判两线段相交,包括端点和部分重合

int intersect_in(point u1,point u2,point v1,point v2){
	if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
		return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
	return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator