TOYS - POJ 2318（计算几何，叉积判断）

题目大意：给你一个矩形的左上角和右下角的坐标，然后这个矩形有 N 个隔板分割成 N+1 个区域，下面有 M 组坐标，求出来每个区域包含的坐标数。

 
分析：做的第一道计算几何题目....使用叉积判断方向，然后使用二分查询找到点所在的区域。
 
代码如下：
============================================================================================================================

#include<stdio.h>

#include<math.h>

using namespace std;

const int MAXN = 5e3+;

const double PI = acos(-1.0);

struct point

{

    double x, y;

    point(int x=, int y=):x(x), y(y){}

};

struct Vector

{

    point a, b;

    void InIt(point t1, point t2){a=t1, b=t2;}

    double operator * (const point &p) const

    {

        return (p.x-b.x)*(a.y-b.y) - (p.y-b.y)*(a.x-b.x);

    }

};

Vector line[MAXN];

int Find(int N, point a)

{

    int L=, R=N;

    while(L <= R)

    {

        int Mid = (L+R) >> ;

        if(line[Mid] * a < )

            R = Mid - ;

        else

            L = Mid + ;

    }

    return R;

}

int main()

{

    int M, N;

    double x1, x2, y1, y2, ui, li;

    while(scanf("%d", &N) != EOF && N)

    {

        scanf("%d%lf%lf%lf%lf", &M, &x1, &y1, &x2, &y2);

        int ans[MAXN]={};

        line[].InIt(point(x1, y1), point(x1, y2));

        for(int i=; i<=N; i++)

        {

            scanf("%lf%lf", &ui, &li);

            line[i].InIt(point(ui, y1), point(li, y2));

        }

        while(M--)

        {

            scanf("%lf%lf", &ui, &li);

            int i = Find(N, point(ui, li));

            ans[i] += ;

        }

        for(int i=; i<=N; i++)

            printf("%d: %d\n", i, ans[i]);

        printf("\n");

    }

    return ;

}

重写...

#include<math.h>

#include<stdio.h>

#include<vector>

#include<iostream>

#include<algorithm>

using namespace std;

const double EPS = 1e-;

const int maxn = ;

int SIGN(const double &val)

{///整数返回1，负数返回-1， 0返回0

    if(val > EPS)return ;

    if(fabs(val) < EPS)return ;

    return -;

}

class Point

{

public:

    Point(double x, double y): x(x), y(y){}

    Point operator- (const Point& other)const

    {///重载减号

        return Point((x-other.x), (y - other.y));

    }

    double operator^(const Point& other)const

    {///重载异或，定义叉积的运算

        return (x*other.y) - (y*other.x);

    }

public:

    double x, y;

};

class Segment

{

public:

    Segment(Point S, Point E) : S(S), E(E){}

    int Mul(Point& other) const

    {///用差乘判断点在线段的方向

        return SIGN( (E-S)^(other-S) );

    }

public:

    Point S, E;

};

class SetSegment

{///定义一个线段的集合，有很多线段构成

public:

    void Insert(const Segment& other)

    {///插入一个线段

        segs.push_back(other);

    }

    unsigned int Find(Point p)

    {///查找点p靠近的最左边的线段的下标

        unsigned int L=, R=segs.size()-, M;

        while(L <= R)

        {

            M = (L+R) / ;

            Segment tmp = segs[M];

            if(tmp.Mul(p) == -)

                R = M-;

            else

                L = M+;

        }

        return R;

    }

public:

    vector<Segment> segs;

};

int main()

{

    int N, M;

    double x1, x2, y1, y2, Ui, Li;

    while(scanf("%d", &N) != EOF && N)

    {

        scanf("%d%lf%lf%lf%lf", &M, &x1, &y1, &x2, &y2);

        SetSegment ss;

        ss.Insert(Segment(Point(x1, y1), Point(x1, y2)));

        for(int i=; i<N; i++)

        {

            scanf("%lf%lf", &Ui, &Li);

            ss.Insert(Segment(Point(Ui, y1), Point(Li, y2)));

        }

        int ans[maxn] = {};

        while(M--)

        {

            scanf("%lf%lf", &x1, &y1);

            int index = ss.Find(Point(x1, y1));

            ans[index] += ;

        }

        for(int i=; i<=N; i++)

            printf("%d: %d\n", i, ans[i]);

        printf("\n");

    }

    return ;

}

TOYS - POJ 2318（计算几何，叉积判断）的相关教程结束。