上海二本分数线-付费调查兼职

黄新军

计算几何基础知识讲义

一．基础知识
1.两点间的距离公式：
已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2)，则P1和P2两点间的距离为
d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
2.线段的中点坐标公式：
已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2)，则线段P1P2的中点坐标为
x=(x1+x2)2 y=(y1+y2)2
3.直线的斜率公式：
已知：平面上的两点的直角坐标分别为P1(x1,y1)，P 2(x2,y2),则线段P1P2所在的直线的斜率为
k=（y2-y1)(x2-x1)
4.直线的点斜式方程:
已知：直线过点P0(x0,y0)，斜率为k,则该直线所在的方程为
y=k(x-x0)+y0=kx+y0-kx0=kx+b(与y轴交点的纵坐标:纵截距)
5、三角形面积

ABAC
1
。当然，还有其他 的许多方法，包括大家熟知的
SabsinC
以及Hero公式。
S
ABC

2
2
Hero公式是令
p
abc
2
，则
Sp(pa)(pb)(pc)
。

6、多边形面积计算
如果一个多边形的顶点是按逆时针（顺时针也可）顺序排列的，那么我们 可以找到一种简洁的面积算
法。

例如右图是一个四边形P
1
P< br>2
P
3
P
4
，设P
5
=P
1
，x
i
是各点在x轴上的射影。我们称P
i
X
i
Xi+1
P
i+1
是一个“有
向梯形”，并定义其面积为：

“有向梯形”的面积是可正可负的，这就是称其“有向”的原因。而整个四边形的面积则是：
这个面积就是正数了。
对于各种特殊的四边形，这个算法仍然成立。这些例子如凹四边形（图 2），被x轴切割的四边形（图
3），注意图3中有向梯形P
1
X
1
X
2
P
2
实际上并不是严格的梯形，但这并不影响结果的正确性，这就是“有 向
梯形”带符号的好处。

黄新军


这个面积算 法对按逆时针排列顶点的四边形的计算结果为正，而对按顺时针排列顶点的四边形的计算
结果为负。此外 ，它也适用于任意多边形。
【结论】：
设多边形顶点按逆时针依次为(x
0
，y
0
)，(x
1
，y
1
)，(x
2< br>，y
2
)，…，(x
n
，y
n
)，其中(x
n
，y
n
)=(x
0
，y
0
)。
那么，多 边形面积为：
n1

(x
i0
i
y
i1< br>y
i
x
i1
)
2

时间和空间复杂度都是O(n)。

【练习】
1.已知:矩形上三点的坐标p1(x1,y1),p2(x2,y2),p3(x3,y3)
(1)求矩形另外一点的坐标p4(x4,y4)。
(2)判断点p(x,y)是在矩形内、矩形外还是在矩形的边上。

多边形面积1918
Description
给出一个简单多边形(没有缺口)，它的边要么是垂直的，要么是水平的。要求计算多边形的面积。
多边形被放置在一个X-Y的卡笛尔平面上，它所有的边都平行于两条坐标轴之一。然后按逆时针方向
给 出各顶点的坐标值。所有的坐标值都是整数(因此多边形的面积也为整数)
Input
输入文件第一行给出多边形的顶点数n(n≤100)。接下来的n行每行给出多边形一个顶点的坐标值X和Y(都为整数并且用空格隔开)。顶点按逆时针方向逐个给出。并且多边形的每一个顶点的坐标值-200≤ x，
y≤200。多边形最后是靠从最后一个顶点到第一个顶点画一条边来封闭的。
Output
输出文件仅有一行，包含一个整数，表示多边形的面积。
Sample Input
10
0 0
4 0
4 1
3 1
3 3
2 3
2 2
1 2
1 3
0 3
Sample Output
9

黄新军

二．矢量叉积
1.【矢量的概念】：
如果一条线段的端点是有次序之分的，我们 把这种线段成为有向线段。如果有向线段p1p2的起点p1
在坐标原点，我们可以把它称为矢量p2。
2.【矢量加减法】：
设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，
矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P，P - Q = - ( Q - P )。
矢量平移
3.【矢量叉积】
y
A
B
0 x
叉积只的是向量OA与向量OB所形成的三角形的面积
定义O点坐标为（0，0），A点坐标为（X1，Y1），B点坐标为（X2，Y2）
则有叉积公式S=（X1 Y2-X2 Y1）2
当角AOB∈（0，π）差集为负，称OA在OB的逆时针方向
当角AOB∈（π，2π）叉积为正，称OA在OB的顺时针方向
当角AOB∈{0,π}叉积为0，称点A在直线OB上（判断点是否在直线上）


已知：平面上的两点的直角坐标分别为p1(x1,y1)，p2(x2,y2)则
（1）该两点相对坐标原点(0,0)的叉积为m=x1*y2-x2*y1
若m>0 则相对坐标原点,点p1在点p2的顺时针方向
若m<0 则相对坐标原点,点p1在点p2的逆时针方向
若m=0 则原点和p1、p2在一条直线上
（2）该两点相对点p0(x0,y0)的叉积为m=(x1-x0)*(y2-y0)-(x2-x0 )*(y1-y0)
若m>0 则相对p0点,点p1在点p2的顺时针方向
若m<0 则相对p0点,点p1在点p2的逆时针方向
若m=0 则p0和p1、p2在一条直线上
4. 折线段的拐向判断
确定两条连续的有向线段p0p 1和p1p2在pl点是向左转还是向右转的方法可以直接由矢量叉积的性
质推出。对于有公共端点的线 段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐
向：

黄新军


（1）计算叉积m=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0)
（2）判断m
若m>0 则p1点向左拐
若m<0 则p1点向右拐
若m=0 则点p0、p1、p2在一条直线上

5.判断两线段是否相交
两条线段AB、CD，相交的充要条件是：A、B在直线CD的异 侧且C、D在直线AB的异侧。也就是
说从AC到AD的方向与从BC到BD的方向不同，从CA到CB 的方向也与从DA到DB的方向不同。
这可以通过矢量的叉积来判断：(AC*AD)*(BC*BD )<0且(CA*CB)*(DA*DB)<0

黄新军




struct pos点
{ double x,y;}x座标与Y座标值
struct line线段
{pos: a,b;}

pos p1,p2
line l1,l2;

double multi(pos p1,p2,p0)叉积
{return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}

bool across(line l1,l2)l1,l2是否有交点
{
*
线段l1,l2的界限框同时在x,y方向上相交才可能有交点
以l1的a点为 公共点p0,l2的a点为p1,l1的b点为p2作叉积与以l1的a点为公共点p0,l1的b点为p1,l 2
的b点为p2作叉积相乘.若大于0则l2跨立l1
以l2的a点为公共点p0,l1的a 点为p1,l2的b点为p2作叉积与以l2的a点为公共点p0,l2的b点为p1,l1
的b点为p 2作叉积相乘.若大于0则l1跨立l2
*
if ((max(l1.a.x,l1.b.x)>=min(l2.a.x,l2.b.x)&& (min(l1.a.x,l1.b.x)<=max(l2.a.x,l2.b.x)
&&(max(l1.a.y,l1.b.y)>=min(l2.a.y,l2.b.y) &&(min(l1.a.x,l1.b.y)<=max(l2.a.x,l2.b.y)&&
(multi(l2.a,l1.b,l1.a)*multi(l1.b,l2.b,l1.a)>0) && (multi(l1.a,l2.b,l2.a)*multi(l2.b,l1.b,l2.a)>0)) return 1;
return 0;
}
int main()
{cin>>l1.a.x>>l1.a.y>>l1.b.x>>l1.b.y;l1的两点座标
cin>>l2.a.x>>l2.a.y>>l2.b.x>>l2.b.y); l1的两点座标
cout< return 0;
}


应用1：
1判断直线与线段是否相交
直线给出的是两个点坐标，把其中 一个定义为原点，判断线段的两个端点是否在直线的同一
方向（顺时针或逆时针），是则线段与直线不想 交，否则相交
2判断线段与线段是否相交
按照判断直线与线段是否相交的方法，分别把线段 1和线段2当成直线，如果线段2的两个
段点在线段1所在直线的两侧，且线段1的两个端点在线段2所 在直线的两侧，则两线段相
交，否则不相交。
3判断点是否在凸多边形内

黄新军

顺时针遍历凸多边形的边，如果对于每条边，所给的点都在其顺时针方向，则点在多边形内

应用2：凸包

三．凸包算法
1.凸包的概念
一个点集Q＝（ p0,p1,p2...p
n-1
)，它的凸包是一个最小的凸多边形P，且满足Q中的每个点 或者在P的
边界上，或者在P的内部。在直观上，我们可以把Q中的每个点看作露在板外的铁钉．那么凸 包就是包含
所有铁钉的一个拉紧的橡皮绳所构成的形状．
如图：
2.寻找凸包算法
算法如下(极角序Graham-Scan算法):
1)求q中y坐标最小的点p0,若具有最小坐标的点有多个,则取最左边的点作为p0.
2 )对q中剩余的点按逆时针相对p0的极角排序,若有数个保留其中距p0最远的点得到序列
(p1,p 2,...pn-1);
3)p0,p1,p2相继入栈
4)for i=3 to n-1 do
错误！未找到引用源。 while 由次栈顶元素、栈顶元素和Pi所形成角不是向左转do栈顶元素出栈s；
错误！未找到引用源。pi入栈
5)打印按逆时针排列的栈中的各顶点
1、找出点集Q中处 于最低位置(Y坐标值最小)的一个点P0是凸包ch(Q)的一个顶点。如果这样的顶点有
多个，则选 取最左边的点为P0。
2、各点依据逆时针方向上相对P0的极角的递增次序排列成Q。极角的大小通 过计算叉积(Pi-P0)*(Pj-P0）
确定:
若叉积>0，则说明相对P0来说，Pj的极角大于Pi的极角，Pi先于Pj被扫描;
若叉积<0，则说明Pj的极角小于Pi的极角，Pj先于Pi被扫描;
若叉积=0，则说明 两个极角相等。在这种情况下，由于Pi和Pj中距离P0较近的点不可能是凸包的
顶点，因此只需扫描 其中一个与P0距离较远的点。

黄新军

3、按照Q序列顺序确定凸包顶点。堆栈S存储凸包顶点。初始时P0和排序后的P1、P2相继入栈。 扫描
过程中，Q集合中的其它点都被推入堆栈一次，而不是凸包ch(Q)顶点的点最终将弹出堆栈。判 别栈顶元
素是否为凸包顶点的方法：
若栈顶元素向左转指向当前被扫描的点Pi，则 为凸包顶点，即(P
i
-P
top-1
)*(P
top
-P
top-1
)<0；
否则（(P
i
-P
top- 1
)*(P
top
-P
top-1
) ≥0）栈顶元素不属于凸包顶点，从堆栈S中移出。
在弹出了所有非左转的顶点后，我们就把 Pi推入堆栈S，继续扫描序列中的下一个点P
i+1
。当算法结
束时，堆栈S中仅包 含ch(Q)的顶点，其顺序为各点在边界上出现的逆时针方向排列的顺序。

黄新军


极角序Graham-Scan算法
const int Maxn=2000;
struct point
{
double x,y;
};
point a[Maxn];存储点坐标
int b[Maxn];栈，存储点的顺序号
int n,tot;

void init()
{
int min=1;
cin>>n;
for(int k=0;k {
cin>>a[k].x>>a[k].y;
if ((a[min].y>a[k].y) ||(a[min].y=a[k].y&&a[min].x>a[k].x))min=k;
}
point temp;
temp=a[0],a[0]=a[min],a[min]=temp;
}

int chaji(const void &p0,const void &p1,const void &p2)
{
point *a,*b,*c;
a=(point)p0,b=(point)p1,c=(point)c;
return (b->x-a->x)*(c->y-a->y)-(b->y-a->y)*(c->x-a->x);
}

黄新军

int compare(const void &a,const void &b)
{
return(chaji(&a[0],a,b));
}


int gram()
{

int i;
tot=2; b[0]=0; b[1]:=1;
for(i=2;i {
whil e((tot>1)&&!(chaji(a[b[tot-1]],a[b[tot]],a[i])) tot--;
tot++; b[tot]=i;
}
}

int main()
{
init();
qsort(a+1,n-1,sizeof(point),compare);按极角序对点排序
gram();
for(int i=0;i}


方法二：
水平序Graham-Scan算法
将所有的点按y坐标从小到大排序, y相同则按x从小到大排。从最小一个y开始，按排好的序从小到大，
用上面的栈的方法做凸包，一次以 后，得到凸包的右链。然后用相同的方法，按y从大到小顺序再做一次，
得到凸包的左链。两条链拼在一 起就是凸包了。
与极角序相比 时间复杂度虽然和上面相同，但这种算法更优。其优势在于：1、 排序方法更简单；2、
避免了一些特殊情况
【参考代码】
水平序Graham- Scan算法

const int Maxsize = 201
struct Point
{
int x , y
};
inline Point operator - ( const Point &a , const Point &b )
{
Point c
c . x = a . x - b . x
c . y = a . y - b . y
return c
}
inline int operator *( const Point &a , const Point &b )
{
return a.x * b.y - a.y * b.x
}

黄新军

Point P[ Maxsize ] 存储点坐标
int Stack[ Maxsize ] 栈，存储点的顺序号
int top , N
inline bool TurnRight( const Point &a, const Point &b , const Point &c )
{
if( ( c - a ) * ( b - a ) >= 0 ) return true
return false
}
void ConvexHull()
{
bool Used[ Maxsize ]
memset( Used , false , sizeof( Used ) )
int k , MaxTop
for( int i = 1 i < N i++ )
for( int j = 1 j <= N - i j++ )
if( P[ j ].y > P[ j+1 ].y || P[ j ].y == P[ j+1 ].y && P[ j ].x > P[ j+1 ].x ) 按从下到上，从左到右顺
序对点排序
swap( P[ j ] , P[ j+1 ] )
寻找右链，栈的第一个元素为最左下角点编号
Stack[ 1 ] = 1
k = 2
top = 1
while( k <= N )
{
while( top > 1 && TurnRight( P[ Stack[ top - 1 ] ] , P[ Stack[ top ] ] , P[ k ] ) )
Used[ Stack[ top-- ] ] = false 与栈顶两个点形成右拐则出栈
Stack[ ++top ] = k 当前点入栈
Used[ k ] = true
k ++
从下往上扫描
}
寻找左链，栈的第一个元素为最右上角点编号
MaxTop = top
k = N - 1
while( k >= 1 )
{
while( Used[ k ] ) k --
while( top > MaxTop && TurnRight( P[ Stack[ top - 1 ] ] , P[ Stack[ top ] ] , P[ k ] ) )
Used[ Stack[ top-- ] ] = false 与栈顶两个点形成右拐则出栈
Stack[ ++top ] = k 当前点入栈
Used[ k ] = true
k --
从上往下扫描
}
}

黄新军



【练习试题】
轰炸1034
Description
“我该怎么办？”飞行员klux向你求助。
事实上，klux面对的是一个很简单的问题，但是他实在太菜了。
klux要想轰炸某个 区域内的一些地方，它们是位于平面上的一些点，但是（显然地）klux遇到了抵抗，
所以klux只 能飞一次，而且由于飞机比较破，一点起飞就只能沿直线飞行，无法转弯。现在他想一次轰炸
最多的地方 。
Input
第一行 n(1以下n行每行有一对整数，表示一个点的坐标。没有一个点会出现两次。
Output
一个整数，表示一条直线能覆盖的最多的点数。
Sample Input
5
1 1
2 2
3 3
9 10
10 11
Sample Output
3

#include
#define X(a,b) (a.x-b.x)向量减
#define Y(a,b) (a.y-b.y)
using namespace std;
int mx=2;
struct Point
{ int x,y;
}pp[800];定义点
inline bool cross(Point a,Point b,Point c) 叉积判断
{ if(X(b,a)*Y(c,a)-Y(b,a)*X(c,a)==0)return true;

}
return false;
int main()
{
int n,i,j,t,e;
scanf(










for(i=0;iscanf(
if(n<=2)
{ cout<for(i=0;i{ for(j=0;j



{ e=2;
for(t=i+1;t {
if(cross(pp[i],pp[j],pp[t]))e++;

黄新军








}






}



}

}
if(n-t+eif(e>mx)mx=e;
cout<return 0;
机器蛇1922
【问题描述】：在未来的某次战争中，我军计划了一次军事行动，目的是劫持敌人的航母。由于这个计划
高度保密，你只知道你所负责的一部分：机器蛇的通信网络。计划中要将数百条机器蛇投放到航母的各个
角落里。由于航母内部舱室、管线错综复杂，且大部分由金属构成，因此屏蔽效应十分强烈，况且还要考
虑敌人的大强度电子干扰，如何保持机器蛇间的联系，成了一大难题。每条机器蛇的战斗位置由作战计划
部门制定，将会及时通知你。每条机器蛇上都带有接收、发射系统，可以同时与多条机器蛇通讯。由于整
个系统承载的数据量庞大，需要一个固定的通讯网络。情报部门提供了极其详尽的敌方航母图纸，使你对
什么地方有屏蔽了如指掌。
请你设计一个程序，根据以上信息构造通讯网络，要求信息可以 在任意两条机器蛇间传递，同时为了
避免干扰，通讯网络的总长度要尽可能的短。
【文件输 入】：第一行是一个整数n（n≤200）表示参战的机器蛇总数。以下n行，每行两个整数xi，yi，
为第i支机器蛇的战斗位置。接下来一行是一个整数m（m≤100）表示航母内部可能产生屏蔽的位置。最< br>后m行，每行四个整数ai，bi，ci，di，表示线段(ai，bi)-(ci，di)处可能有屏蔽 ，也就是说通讯网络不能跨
越这条线段。
【文件输出】： 仅一个实数，表示建立的通讯网的 最短长度，保留3位小数。如果不能成功建立通讯网，
请输出-1.000。
【样例输入】：
3
1 3
3 1
5 5
1
0 0 3 3
【样例输出】：8.944

【模拟试题】多边形面积1478
Description
在直角坐标系中，给出n个顶点的坐标，求这n个点所围成的图形的周长和面积。
注意：
（1）如果所有点共线则周长按直线的长度计算，面积视为0；
（2）如果部分点共线按共线后的多边形计算；
（3）所给出的n个顶点如果能围成多边形均为突多边形。
Input
第一行输入多边形顶点个数n(3 <= n <= 10);
接下来n行每行输入一个顶点坐标x,y，x,y均为整数且坐标的绝对值均不超过10。
Output
两行，即多边形的周长和面积（均保留两位小数）。
Sample Input
4
0 0
1 0
0 1
1 1
Sample Output

黄新军

4.00
1.00



【2007年四川】最大土地面积2044
Description：在某块平面土地上有n 个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你
希望这四个点围成的多边形面积最大
Input：第1行一个正整数n，接下来n行，每行2个数x、y，表示该点的横坐标和纵坐标。
Output：最大的多边形面积，答案精确到小数点后3位。
Sample Input
5
0 0
1 0
1 1
0 1
0.5 0.5
Sample Output：1.000
【数据范围】 n<=2000，|x|,|y|<=100000

练习:
1.巳知:平面上有n个点(n<=10000)，用Graham算法找出彼此间最远的两个点.
多边形面积

【曙光试题】两个凸多边形交的面积1140
Description
在平面上有两给定的凸多边形，若两凸多边形相交，则它们的 交集也是一个凸多边形。若两凸多边形
不相交，指的是两凸多边形相离或仅限于边界点与边上相交，则相 交面积为0。如图所示： 你的任务是编
程给出交集多边形的面积。

两给定的凸多边形按顺时针方向依次给出多边形每个顶点的坐标。
Input
第一 行为一整数M，表示第一个凸多边形的边数，以后M行分别给出了M个顶点的坐标；接着，给
出第二个凸 多边形的边数N，以后N行分别给出了N个顶点的坐标。
Output
只一个数据即交集面积，保留两位小数点。
Sample Input
4
0 0
0 1
1 1
1 0
4
-0.5 -0.5
-0.5 0.5
0.5 0.5
0.5 -0.5
Sample Output
0.25

黄新军

寻找最近点对
Description：给定平面上n个点,找出其中的一对点的距离,使得 在这n个点的所有点对中,该距离为所有点
对中最小的。
Input：第一行：n；2≤n≤60000,接下来n行：每行两个实数：x y,表示一个点的行坐标和列坐标,中间用一
个空格隔开。
Output：仅一行,一个实数,表示最短距离,精确到小数点后面2位
Sample Input
3
1 1
1 2
2 2
Sample Output:1.00
【分析】很直观，这个问题就是平面内有一堆点，让我们找出距离最近的两个点。
 为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n
个实数 x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。
 假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子问题的思想，用S
中各点坐标的中位数来作分割点。
 递归地在S1和S2上 找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S
中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3 ∈S1且q3∈S2。
 能否在线性时间内找到p3,q3？
 如果S的最接近点对是 {p3,q3}，即|p3-q3|p3∈(m-d, m]，q3∈(m,m+d]。
 由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必 有两点距离小于d），并
且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一个点。由 图可以看出，如果(m-d,m]中
有S中的点，则此点就是S1中最大点。
 因此，我们 用线性时间就能找到区间(m-d,m]和(m,m+d]中所有点，即p3和q3。从而我们用
线性时 间就可以将S1的解和S2的解合并成为S的解。
下面来考虑二维的情形。
 选取一垂直 线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为
S1和S2。
 递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近 点对或者是
d，或者是某个{p,q}，其中p∈P1且q∈P2。
 能否在线性时间内找到p,q？
 考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候 选者，则必有distance(p，q)
＜d。满足这个条件的P2中的点一定落在一个d×2d的矩 形R中
 由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多 只
有6个S中的点。
 因此，在分治法的合并步骤中最多只需要检查6×n2=3n个候选者

黄新军


证明:将矩形R的长为2d的边3等分，将它的 长为d的边2等分，由此导出6个(d2)×(2d3)的矩形。
若矩形R中有多于6个S中的点，则由 鸽舍原理易知至少有一个(d2)×(2d3)的小矩形中有2个以上
S中的点。设u，v是位于同一小 矩形中的2个点，则
distance(u,v) 为了确 切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与
p点一起构成最 接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l
上投影点的距离小于 d。由上面的分析可知，这种投影点最多只有6个。
 因此，若将P1和P2中所有S中点按其y坐 标排好序，则对P1中所有点，对排好序的点列作
一次扫描，就可以找出所有最接近点对的候选者。对P 1中每一点最多只要检查P2中排好序的相继
6个点。







double cpair2(S)
{
n=|S|;
if (n < 2) return ;
1、m=S中各点x间坐标的中位数;
构造S1和S2；S1={p∈S|x(p)<=m}, S2={p∈S|x(p)>m}
2、d1=cpair2(S1);
d2=cpair2(S2);
3、dm=min(d1,d2);
4、设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；
P2是S2中距分割线l的距离在dm之内所有点组成的集合；
将P1和P2中点依其y坐标值排序；
并设X和Y是相应的已排好序的点列； < br>5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完
成 合并；
当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；
设dl是按这种扫描方式找到的点对间的最小距离；
6、d=min(dm,dl);
return d;
}
#include
#include
#include
using namespace std;
const int maxn=100001;
struct atp{double x,y;};
int n;
atp a[maxn],tmp[maxn];
void init()读入
{ int i;

黄新军

for(i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
}
void qsortx(int l,int r)快排
{ int i,j;
double x;
atp t;
i=l;j=r;
x=a[(l+r)2].x;
while(i<=j)
{
while(a[i].x while(a[j].x>x)j--;
if(i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}
if(i if(l}
void qsorty(int l,int r)快排
{ int i,j;
double x;
atp t;
i=l;j=r;
x=tmp[(l+r)2].y;
while(i<=j)
{
while(tmp[i].y>x)i++;
while(tmp[j].y if(i<=j)
{
t=tmp[i];tmp[i]=tmp[j];tmp[j]=t;
i++;j--;
}
}
if(i if(l}
double find(int l,int r)
{ int i,j,midd,tot;
double t,minn,xit;
if(l+1==r)只有两个点时特殊处理
return sqrt((a[l].x-a[r].x)*(a[l].x-a[r].x)+(a[l]. y-a[r].y)*(a[l].y-a[r].y));
if(l+2==r)只有三个点时特殊处理
{
minn=100000000;
for(i=l;i<=r-1;i++)
for(j=i+1;j<=r;j++)
{
t=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j ].y)*(a[i].y-a[j].y));
if(t }
return minn;
}
midd=(l+r)2;
xit=(a[midd].x+a[midd+1].x)2; 否则二分
minn=find(l,midd);

黄新军

t=find(midd+1,r);
if(t tot=0;
for(i=l;i<=r;i++)记录在矩形内的点
if(abs(a[i].x-xit) {
tot++;
tmp[tot].x=a[i].x;
tmp[tot].y=a[i].y;
}
if(tot>1)qsorty(1,tot); 以Y坐标为关键字从大到小排序
for(i=1;i<=tot-1;i++)求i点和下面7个点的距离
for(j=i+1;j<=i+7;j++)
{
if(j>tot)break;
t=sqrt((tmp[i].x-tmp[ j].x)*(tmp[i].x-tmp[j].x)+(tmp[i].y-tmp[j].y)*(tmp [i].y-tmp[j].y));
if(t }
return minn;
}
int main()
{ cin>>n;
init();
qsortx(1,n); 以X坐标为关键字从小到达排序
cout< return 0;
}