叉乘题

向量叉乘 1086
题意：给出几条线段的始末点坐标，求解这几条线段共有几个交点。
解题需要使用到向量的叉乘关系：a×b=（|a||b|sinθ）已知两条向量的叉乘结果为正，那么这两条向量的夹角是锐角，为负，则是钝角。
在题目中，假设两条线段,若满足相交，那么有：将其中一条线段固定，另一条线段的两个端点在该线段的两边。

如图：那么，其与固定线段的夹角应为一个锐角一个钝角，叉乘的结果即为一正一负。可以就此排除掉不符合的情况，那么，下一步再次将另一条线段固定，做同样的判断，为了避免如下情况的发生：

所以可以进一步得出实现的方法：

#include <stdio.h>
#include <string.h>
struct 
{
    double x1,y1;
    double x2,y2;
}nu[105];

void main()
{
    int count;
    int i,j,n;
    double k;
    while (scanf("%d",&n)!=EOF&&n!=0)
    {
        count=0;
        memset(nu,0,sizeof (nu));
        for (i=0;i<n;i++)
            scanf ("%lf%lf%lf%lf",&nu[i].x1,&nu[i].y1,&nu[i].x2,&nu[i].y2);
        for (i=0;i<n; +i++)
        {
            for (j=i+1;j<n;j++)
            {
                k=((nu[i].x2-nu[i].x1)*(nu[j].y1-nu[i].y1)-(nu[j].x1-nu[i].x1)*(nu[i].y2-nu[i].y1))*((nu[i].x2-nu[i].x1)*(nu[j].y2-nu[i].y1)-(nu[j].x2-nu[i].x1)*(nu[i].y2-nu[i].y1));
                if (k>0)
                    continue;
                k=((nu[j].x2-nu[j].x1)*(nu[i].y1-nu[j].y1)-(nu[i].x1-nu[j].x1)*(nu[j].y2-nu[j].y1))*((nu[j].x2-nu[j].x1)*(nu[i].y2-nu[j].y1)-(nu[i].x2-nu[j].x1)*(nu[j].y2-nu[j].y1));
                if (k>0)
                    continue;
                count++;
            }
        }
        printf("%d\n",count);
    }
}

2036 改革春风吹满地
题意：给出一个多边形的边数和每一个定点的坐标值，求这个多边形的面积。
同样是叉乘的考试，由于两个向量的叉乘结果为该向量组成的平行四边形的面积，本题的解题思路在于将整个多边形分割成多个三角形，求出各个三角形的面积后做和即得最终解。
可任意选择一个顶点为固定的顶点，并开始分割：

#include <stdio.h>

struct
{
    int x;
    int y;
}nu[100];

double vaca(int i,int j)
{
    return (nu[i].x-nu[0].x)*(nu[j].y-nu[0].y)-(nu[j].x-nu[0].x)*(nu[i].y-nu[0].y);    
}

void main()
{
    int i,j,k,n,m;
    double sum;
    while (scanf("%d",&n)&&n!=0)
    {
        sum=0;
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&nu[i].x,&nu[i].y);
        }
        for (i=1;i<n-1;i++)
            sum+=vaca(i,i+1);
        printf ("%.1lf\n",0.5*sum);
    }
}