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