学步园

     给定n条线段，求解所有线段的交点个数。不是直线，直线的话太容易了，只要斜率 不一样便是相交。

     两条线段相交也就意味着一个线段的两个端点跨立另一条线段的两侧。于是向量叉积的几何意义便得到了运用。如果两个点P1，P2在一条线段Q1Q2两侧，那么向量P1Q1*P1Q2必然和P2Q1*P2Q2异号，或者其中一者为零，那么P1， P2必然在线段Q1Q2的两侧。在判断Q1Q2是否在P1P2的两侧便可判断两线段是否相交。

    题目ＵＲＬ：http://acm.hdu.edu.cn/showproblem.php?pid=1086

     这是我的AC代码。欢迎拍砖。

#include<iostream>
#include<stdio.h>
using namespace std;

const int Max = 110;

struct Point
{
	double x, y;
};

struct Segment
{
	Point s, e;
};

Segment s[Max];

double product(Point &a, Point &b, Point &c)
{
	double x1, y1, x2, y2;
	x1 = a.x - c.x, y1 = a.y - c.y;
	x2 = b.x - c.x, y2 = b.y - c.y;
	return x1 * y2 - y1 * x2;
}

bool intersect(Segment &a, Segment &b)
{
	return product(a.s, a.e, b.s) * product(a.s, a.e, b.e) <= 0 && 
		product(b.s, b.e, a.s) * product(b.s, b.e, a.e) <= 0;
}

int main()
{
	int n, cnt;
	while(scanf("%d", &n) && n)
	{
		for(int i=0; i<n; i++) 
			scanf("%lf %lf %lf %lf", &s[i].s.x, &s[i].s.y, &s[i].e.x, &s[i].e.y);
			
		cnt = 0;
		for(int i=0; i<n; i++)
			for(int j=i+1; j<n; j++)
				if(intersect(s[i], s[j])) cnt ++;
		printf("%d\n", cnt);
	}
	system("pause");
	return 0;
}