关于计算几何的基本理论:http://dev.gameres.com/Program/Abstract/Geometry.htm(点击打开链接)
问题描述:http://acm.hdu.edu.cn/showproblem.php?pid=1086
思路分析: 给定n条线段,求解所有线段的交点个数。不是直线,直线的话太容易了,只要斜率 不一样便是相交。两条线段相交也就意味着两条线段相互跨立,即:一个线段(P1P2)的两个端点跨立另一条线段(Q1Q2)的两侧,同时也满足线段(Q1Q2)的两个端点也要跨立在线段(P1P2)的两侧。于是向量叉积的几何意义便得到了运用。如果两个点P1,P2在一条线段Q1Q2两侧,那么向量P1Q1*P1Q2必然和P2Q1*P2Q2异号,或者其中一者为零,那么P1,
P2必然在线段Q1Q2的两侧。在判断Q1Q2是否在P1P2的两侧便可判断两线段是否相交。
叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:
若 P × Q > 0 , 则P在Q的顺时针方向。(右手定则,叉积大于零代表大拇指向上,即Z的值是正值,四指由P到Q)
若 P × Q < 0 , 则P在Q的逆时针方向。(右手定则,叉积小于零代表大拇指向下,四指由P到Q)
若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向。#include<iostream>
#include<cstdio> 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; }