[HDU]1086You can Solve a Geometry Problem too

http://acm.hdu.edu.cn/showproblem.php?pid=1086

这道题真是让我彻底无解了，我是一开始直接算出2直线的向量，然后进行X乘，错误N次后，看了别人的博客，发现他们说什么判断点在直线2边，回头一看题目，才发现原来这题所说的是线段！

线段的话，我们应该怎么判断是否相交呢？我们可以将一条线段a固定，然后判断另一条线段b的2端点在线段a的位置，如果一个在如果2点都同侧，那必定不相交。

设线段端点为从 A(x1[i], y1[i])到 B(x2[i], y2[i]), 线外一点 P(x1[j]，y1[j])，
判断该点位于有向线 A→B 的那一侧。
a = ( x2[i]-x1[i], y2[i]-y1[i])
b = (x1[j]-x1[i], y1[j]-y1[i])
a x b = | a | | b | sinφ (φ为两向量的夹角)
| a | | b |  ≠ 0 时，  a x b  决定点 P的位置
所以  a x b  的方向大小z决定 P位置
(x2[i]-x1[i])(y1[j]-y1[i]) – (y2[i]-y1[i])(x1[j]-x1[i])  >  0   左侧
(x2[i]-x1[i])(y1[j]-y1[i]) – (y2[i]-y1[i])(x1[j]-x1[i])  >  0   右侧
(x2[i]-x1[i])(y1[j]-y1[i]) – (y2[i]-y1[i])(x1[j]-x1[i])  >  0   线段上

上述为取线段一段点P(x1[j]，y1[j])进行判断，还有一点P(x2[j]，y2[j])也是一样的。

#include"stdio.h"
#include"stdlib.h"
#include"math.h"
int main()
{
    int n,i,j,count; 
    double x1[110],y1[110],x2[110],y2[110],temp;
    while(scanf("%d",&n)&&n)
    {
         for(i=0;i<n;i++)
            scanf("%lf%lf%lf%lf",&x1[i],&y1[i],&x2[i],&y2[i]);
         count=0;
         for(i=0;i<n;i++)
         for(j=i+1;j<n;j++)           
         {
             temp=((x2[i]-x1[i])*(y1[j]-y1[i])-(x1[j]-x1[i])*(y2[i]-y1[i]))*((x2[i]-x1[i])*(y2[j]-y1[i])-(x2[j]-x1[i])*(y2[i]-y1[i]));//比较繁琐，就是上面分析的内容 
             if(temp>0)
             continue; 
             temp=((x2[j]-x1[j])*(y1[i]-y1[j])-(x1[i]-x1[j])*(y2[j]-y1[j]))*((x2[j]-x1[j])*(y2[i]-y1[j])-(x2[i]-x1[j])*(y2[j]-y1[j]));//2边调换. 
             if(temp>0)
             continue;
             count++;
         }
         printf("%d\n",count);
    }
}

[HDU]1086You can Solve a Geometry Problem too

推荐阅读