计算几何----线段交-白红宇

计算几何----线段交

阅读量：4933 次

发布时间：2019-06-11

本文共 1311 字，大约阅读时间需要 4 分钟。

[ ] [ ] [命题人:

]

题目描述

给定N个线段。求有交点的线段对数。

保证没有两条线段共线

输入

一行一个整数N，表示线段的个数

第2~N+1行，每行四个实数，x1,y1,x2,y2，表示线段的两个端点(x1,y1)和(x2,y2)

输出

一行一个整数，表示有交点的线段对数。

样例输入

复制样例数据

30.00 0.00 1.00 1.000.00 1.00 1.00 0.000.00 0.00 1.00 0.00

样例输出

提示

(0,0)(1,1)和(0,1)(1,0)有交点

(0,0)(1,1)和(0,0)(1,0)有交点

(0,1)(1,0)和(0,0)(1,0)有交点

对于100%的数据，N≤100

点的坐标范围(−10000,10000)

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #define Inf 0x3f3f3f3f const int maxnn=1e5+5;typedef long long ll;using namespace std;struct node{ double x; double y;}; node a,b,c,d;node p1[105],p2[105];double minn(double xx,double yy){ if(xx
               
                yy) { return xx; } else { return yy; }}bool judge(node a,node b,node c,node d){ if(minn(a.x,b.x) <= maxx(c.x,d.x) && minn(c.x,d.x) <= maxx(a.x,b.x) && minn(a.y,b.y) <= maxx(c.y,d.y) &&minn(c.y,d.y)<=maxx(a.y,b.y)) { double u,v,w,z; u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y); v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y); w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y); z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y); return (u*v<=0.00000001 && w*z<=0.00000001); } return false;}int main(){ int N; cin>>N; for(int t=0;t