本文共 1582 字,大约阅读时间需要 5 分钟。
题意:判断两两直线相交的个数
code:
#include#include #include #include #include using namespace std;//点struct POINT{ double x, y; POINT(){ } POINT(double a, double b){ x = a; y = b; }}p[105];//线段struct Seg{ POINT a, b; Seg() { } Seg(POINT x, POINT y){ a = x; b = y; }};//叉乘double cross(POINT o, POINT a, POINT b){ return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);}//判断点在线段上bool On_Seg(POINT a, Seg s){ double maxx = max(s.a.x, s.b.x), minx = min(s.a.x, s.b.x); double maxy = max(s.a.y, s.b.y), miny = min(s.a.y, s.b.y); if(a.x >= minx && a.x <= maxx && a.y >= miny && a.y <= maxy) return true; return false;}//判断线段相交bool Seg_cross(Seg s1, Seg s2){ double cs1 = cross(s1.a, s2.a, s2.b); double cs2 = cross(s1.b, s2.a, s2.b); double cs3 = cross(s2.a, s1.a, s1.b); double cs4 = cross(s2.b, s1.a, s1.b); // 互相跨立 if(cs1 * cs2 < 0 && cs3 * cs4 < 0) return true; if(cs1 == 0 && On_Seg(s1.a, s2)) return true; if(cs2 == 0 && On_Seg(s1.b, s2)) return true; if(cs3 == 0 && On_Seg(s2.a, s1)) return true; if(cs4 == 0 && On_Seg(s2.b, s1)) return true; return false;}int main(){ int n; while(cin >> n, n){ Seg p[105]; for(int i = 0;i < n;i++) cin >> p[i].a.x >> p[i].a.y >> p[i].b.x >> p[i].b.y; int cnt = 0; for(int i = 0;i < n;i++) { for(int j = i+1;j < n;j++) { if(Seg_cross(p[i],p[j])) cnt ++; } } cout << cnt << endl; }}
转载地址:http://lcsgi.baihongyu.com/