这个题目就是基本的线段相交水题。
并且重复点竟然算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#include#includeusing 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; }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 }int main(){int n;while(scanf("%d",for(i=0;i hdu 1086 线段相交,布布扣,bubuko.com