【计算几何+判断线段是否相交】HDU-1086 You can Solve a Geometry Problem too

注解

1、基础计算几何问题，判断两线段是否相交。
2、《算法竞赛入门到进阶》第11章有线段相交的模板。
3、主要思想是利用叉积有正负的特点，如果一条线段的两端在另一条线段的两侧，那么两个端点与另一线段产生的两个叉积正负相反，也就是说两个叉积相乘为负。如果两条线段互相满足这一点，那么就是相交的。

代码

#include <iostream>
#include <cmath>

using namespace std;

int sgn(double x) {
	if(abs(x)<1e-8)
		return 0;
	else
		return x<0?-1:1;
}

struct Point {
	double x, y;

	Point() {}

	Point(double x, double y):x(x),y(y) {}

	Point operator - (Point B) {
		return Point(x-B.x, y-B.y);
	}
};

typedef Point Vector;

double Cross(Vector A, Vector B) {
	return A.x*B.y-A.y*B.x;
}

int Cross_segment(Point a, Point b, Point c, Point d) { //Line1:ab; Line2:cd
	double c1 = Cross(b-a, c-a), c2 = Cross(b-a, d-a);
	double d1 = Cross(d-c, a-c), d2 = Cross(d-c, b-c);
	return sgn(c1)*sgn(c2)<=0 && sgn(d1)*sgn(d2)<=0;
}

struct Line {
	Point p1, p2;
	Line() {}
	Line(Point p1, Point p2):p1(p1),p2(p2) {}
};

int main() {

	int n;
	cin>>n;
	while(n) {
		int ans = 0;
		
		Line line[n];
		
		for(int i=0; i<n; i++) {
			double x1, y1, x2, y2;
			cin>>x1>>y1>>x2>>y2;
			Point p1(x1, y1);
			Point p2(x2, y2);
			line[i].p1 = p1;
			line[i].p2 = p2;
		}
		
		for(int i=0; i<n-1; i++){
			for(int j=i+1; j<n; j++){
				if(Cross_segment(line[i].p1, line[i].p2, line[j].p1, line[j].p2)){
					ans++;
				}
			}
		}
		
		cout<<ans<<endl;

		cin>>n;
	}

	return 0;
}

结果