题目大意：给你一个矩形的左上角和右下角的坐标，然后这个矩形有 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 ;
}