| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
两线段相交的模板(包含端点)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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator