题意:
给你几条线段,让你求出这些线段的所有交点数。例如输入样例:先输入一个n,代表有n条线段,接着每一行输入一天线段,每两个数代表一个端点,0.00 0.00 1.00 1.00,代表着以0.00,0.00)和(1.00,1.00)为两个端点的一条线段。
思路:
由两个端点可以求出这条线段所在的直线方程,并由这两个端点确定可行区间。对所有的直线两两联立求得任意两条直线之间是否有交点,并且判断该交点是否合法(在可行区间),同时判断该点是否曾经被记录,若没被记录,交点数加1,并把这个交点记录下来。
代码实现:
#include <iostream> using namespace std; const int MAXN = 100 + 10; typedef struct point { double x,y; }point; point p[MAXN * MAXN]; typedef struct segment { double a,b,c,d; }segment; segment se[MAXN]; //保存线段线段 void f(segment A, segment B, int &cnt) //两条线段和当前交点数 { double x,y; //联立求解x,y if ((A.a - A.c) / (A.b - A.d) == (B.a - B.c) / (B.b - B.d)) //A、B平行 { return; } if (A.a - A.c ==0 && B.a - B.c != 0) //A线段为竖直线且B线段不为竖直线 { x = A.a; y = (B.b - B.d) * (x - B.a) / (B.a - B.c) + B.b; } else if(B.a - B.c == 0 && A.a - A.c !=0) //B线段为竖直线且A线段不为竖直线 { x = B.a; y = (A.b - A.d) * (x - A.a) / (A.a - A.c) + A.b; } else { x = (B.a * (B.b - B.d) / (B.a - B.c) - A.a * (A.b - A.d) / (A.a - A.c) + A.b - B.b) / ((B.b - B.d) / (B.a - B.c) - (A.b - A.d) / (A.a - A.c)); y = (B.b - B.d) / (B.a - B.c) * (x - B.a) + B.b; } int flag = 1; if (x - A.a >= 0 && A.c - x >= 0 && x - B.a >= 0 && B.c - x >= 0) { for (int i = 0; i < cnt; i++) //判断是否被标记 { if (p[i].x - x == 0 && p[i].y - y == 0) { flag = 0; break; } } if (flag) //没有被标记,保存下来 { p[cnt].x = x; p[cnt].y = y; cnt++; } } } int main() { int n; while (cin>>n && n) { for (int i = 0; i < n; i++) { scanf("%lf%lf%lf%lf",&se[i].a, &se[i].b, &se[i].c, &se[i].d); if (se[i].a > se[i].c) //保证a<c,b<d { double m = se[i].a; se[i].a = se[i].c; se[i].c = m; m = se[i].b; se[i].b = se[i].d; se[i].d = m; } } int cnt = 0; for (int i = 0; i < n; i ++) { for (int j = i + 1; j < n; j++) { f(se[i], se[j], cnt); } } cout<<cnt<<endl; } return 0; }