问题 C: 线段交

时间限制: 1 Sec  内存限制: 128 MB
[提交] [状态] [命题人:]

题目描述

给定N个线段。求有交点的线段对数。
保证没有两条线段共线

 

输入

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

 

输出

一行一个整数，表示交点的个数。

 

样例输入

复制样例数据

3
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.00
0.00 0.00 1.00 0.00

样例输出

3

 

提示

(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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const double eps = 1e-10;
struct point{
    double x, y;
};
struct Line{
    point l;
    point r;
};
double min(double a, double b){
    return a < b ? a : b;
}
 
double max(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 && j * k <= eps;
}
int main(){
    int n;
    Line line[110];
    while(cin>>n&&n){
        for(int i=1;i<=n;i++){
            cin>>line[i].l.x>>line[i].l.y>>line[i].r.x>>line[i].r.y;
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(inter(line[i].l,line[i].r,line[j].l,line[j].r))
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }
}