Description:

Many geometry（几何）problems were designed in the ACM/ICPC. And now, I also prepare a geometry problem for this final exam. According to the experience of many ACMers, geometry problems are always much trouble, but this problem is very easy, after all we are now attending an exam, not a contest 😃
Give you N (1<=N<=100) segments（线段）, please output the number of all intersections（交点）. You should count repeatedly if M (M>2) segments intersect at the same point.

Note:
You can assume that two segments would not intersect at more than one point.

Input:

Input contains multiple test cases. Each test case contains a integer N (1=N<=100) in a line first, and then N lines follow. Each line describes one segment with four float values x1, y1, x2, y2 which are coordinates of the segment’s ending.
A test case starting with 0 terminates the input and this test case is not to be processed.

Output:

For each case, print the number of intersections, and one line one case.

Sample Input:

2
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.00
3
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.000
0.00 0.00 1.00 0.00
0

Sample Output:

1 3

题目链接

判断n条线段有多少个交点，暴力判断任两条线段是否有交点，题目数据没有交点重合的情况，代码没有去重。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e2+5;
const int mod = 1e9+7;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
}

struct point {
    double x, y;
};

struct edge {
    point a, b;
}p[maxn];

int n;
int ans;

bool judge(edge a, edge b) {
    if (min(a.a.x, a.b.x) > max(b.a.x, b.b.x) || min(a.a.y, a.b.y) > max(b.a.y, b.b.y) || min(b.a.x, b.b.x) > max(a.a.x, a.b.x) || min(b.a.y, b.b.y) > max(a.a.y, a.b.y)) {
        return 0;
    }
    double h, i, j, k;
    h = (a.b.x - a.a.x) * (b.a.y - a.a.y) - (a.b.y - a.a.y) * (b.a.x - a.a.x);
    i = (a.b.x - a.a.x) * (b.b.y - a.a.y) - (a.b.y - a.a.y) * (b.b.x - a.a.x);
    j = (b.b.x - b.a.x) * (a.a.y - b.a.y) - (b.b.y - b.a.y) * (a.a.x - b.a.x);
    k = (b.b.x - b.a.x) * (a.b.y - b.a.y) - (b.b.y - b.a.y) * (a.b.x - b.a.x);
    return h * i <= eps && j * k <= eps;
}

int main() {
    //fre();
    while (~scanf("%d", &n) && n) {
        ans = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%lf%lf%lf%lf", &p[i].a.x, &p[i].a.y, &p[i].b.x, &p[i].b.y);
        }
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (judge(p[i], p[j])) {
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}