计算几何之叉积（外积）得应用

这几天学了一下计算几何，很多内容以前都接触过，但是这么多得定理和意义却从来没想到过，也是吃惊得学习了一场

叉积（外积）是一个具有大小和方向得量，方向和点a,b所在得平面垂直，满足右手螺旋定则

a * b得叉积是

double cross(Point p0,Point p1,Point p2)
{
    Point a,b;
    a = p1 - p0;
    b = p2 - p0;
    return a.x * b.y - b.x * a.y;
}

 因为叉积经常来判断一个点和一个线段/射线/直线得位置——顺时针防线/逆时针防线

返回的值如果大于0，代表p2这个点在线段p0 - p1得逆时针防线，小于零是顺时针方向，等于零就代表重合了

用这个题加二分就可以解决一下POJ2398

题目大意：就是问题由纸片分开的各个区域有多少玩具，只是输出要换个形式而已（也就是个模板的嵌套吧）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <string.h>
#define eps 1e-10
#define equal(a,b) (fabs((a) - (b))) < eps
using namespace std;
const int maxn = 5e3 + 1e2;
class Point{
    public:
    int x,y;//不要忘记赋初始值
    Point(int x = 0,int y = 0):x(x),y(y){}

    Point operator + (Point a){return Point(x + a.x,y + a.y);}
    Point operator - (Point a){return Point(x - a.x,y - a.y);}
    Point operator * (int a){return Point(x * a,y * a);}
    Point operator / (int a){return Point(x / a,y / a);}
};
int dot(Point a,Point b){return a.x * b.x + a.y * b.y;}
int cross(Point a,Point b){return a.x * b.y - a.y * b.x;}
struct Segment{
    Point p1,p2;
};
Segment S[maxn];
int ret[maxn];
int ans[maxn];
bool judge(int x,int y,int mid)
{
    Point p(x,y);
    Point a = p - S[mid].p1;
    Point b = S[mid].p2 - S[mid].p1;
    //int f=(S[mid].p2.x-S[mid].p1.x)*(y-S[mid.p1.y)-(S[mid].p2.y-S[mid].p1.y)*(x-S[mid].p1.x);

    if(cross(b,a) > 0)return true;
    else return false;
}
void search_toll(int x,int y,int n)
{
    int left = 0,right = n - 1;
    while(left < right - 1)
    {
        int mid = (left + right) >> 1;
        if(judge(x,y,mid))
        {
            right = mid;
        }
        else
        {
            left = mid;
        }
    }
    //cout<<left<<" "<<right<<"$$$$$$"<<endl;
    if(judge(x,y,left))
    {
        ret[0]++;
    }
    else if(judge(x,y,right))
    {
        ret[right]++;
    }
    else
    {
        ret[n]++;
    }
}
bool cmp(Segment a,Segment b)
{
    return a.p1.x < b.p1.x;
}
int main()
{
    int n,m,x1,x2,y1,y2;
    while(~scanf("%d",&n),n)
    {
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        memset(ret,0,sizeof(ret));
        memset(ans,0,sizeof(ans));
        for(int i = 0;i < n;i++)
        {
            int xd,xu;
            scanf("%d%d",&xu,&xd);
            S[i].p1.x = xd;
            S[i].p1.y = y2;
            S[i].p2.x = xu;
            S[i].p2.y = y1;
        }
        sort(S,S + n,cmp);
        for(int i = 0;i < m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            search_toll(x,y,n);
        }
//        for(int i = 0;i <= n;i++)
//        {
//            printf("%d: %d
",i,ret[i]);
//        }
//        printf("
");
        for(int i = 0;i <= n;i++)
        {
            if(ret[i] > 0)ans[ret[i]]++;
        }
        printf("Box
");
        for(int i = 1;i <= n;i++)
        {
            if(ans[i]>0)printf("%d: %d
",i,ans[i]);
        }
    }
    return 0;
}