最近点对、最远点对

算法收集

最近点对

最近点对
使用了分治的算法
里面用了一个STL函数inplace_merge归并函数

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> P;
const double INF = 1e9+10;
const int maxn = 1e4+10;
int n;
P point[maxn];
bool cmp_y(P a, P b){
return a.second<b.second;
}
double cloest_pair(P *point, int n){
if(n<=1) return INF;
int m = n/2;
double x = point[m].first;
double d = min(cloest_pair(point, m), cloest_pair(point+m, n-m));
//归并排序
//inplace_merge()函数将两个连接在一起的排序序列
//[first, middle)和[middle, last)结合成单一序列并保持有序。
//inplace_merge()函数是stable操作。
inplace_merge(point, point+m, point+n, cmp_y);
vector<P> b;
for(int i=0; i<n; i++){
if(fabs(point[i].first-x)>d) continue;
for(int j=0; j<b.size(); j++){
double dx = point[i].first-b[b.size()-j-1].first;
double dy = point[i].second-b[b.size()-j-1].second;
if(dy >= d) break;
d = min(d, sqrt(dx*dx+dy*dy));
}
b.push_back(point[i]);
}
return d;
}
void solve(){
sort(point, point+n);
double ans = cloest_pair(point, n);
if(ans<=1e4){
printf("%.4f\n", ans);
}
else {
printf("INFINITY\n");
}
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n&&n){
for(int i=0; i<n; i++){
cin>>point[i].first>>point[i].second;
}
solve();
}
return 0;
}

最远点对

poj2187
用对踵点旋转求解(凸包上旋转)

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
struct Point
{
int x,y;
Point(int _x = 0, int _y = 0)
{
x = _x;
y = _y;
}
Point operator -(const Point &b)const
{
return Point(x - b.x, y - b.y);
}
int operator ^(const Point &b)const
{
return x*b.y - y*b.x;
}
int operator *(const Point &b)const
{
return x*b.x + y*b.y;
}
void input()
{
scanf("%d%d",&x,&y);
}
};
int dist2(Point a,Point b)
{
return (a-b)*(a-b);
}
const int MAXN = 50010;
Point list[MAXN];
int Stack[MAXN],top;
bool _cmp(Point p1,Point p2)
{
int tmp = (p1-list[0])^(p2-list[0]);
if(tmp > 0)return true;
else if(tmp == 0 && dist2(p1,list[0]) <= dist2(p2,list[0]))
return true;
else return false;
}
void Graham(int n)
{
Point p0;
int k = 0;
p0 = list[0];
for(int i = 1;i < n;i++)
if(p0.y > list[i].y || (p0.y == list[i].y && p0.x > list[i].x))
{
p0 = list[i];
k = i;
}
swap(list[0],list[k]);
sort(list+1,list+n,_cmp);
if(n == 1)
{
top = 1;
Stack[0] = 0;
return;
}
if(n == 2)
{
top = 2;
Stack[0] = 0;
Stack[1] = 1;
return;
}
Stack[0] = 0;
Stack[1] = 1;
top = 2;
for(int i = 2;i < n;i++)
{
while(top > 1 && ((list[Stack[top-1]]-list[Stack[top-2]])^(list[i]-list[Stack[top-2]])) <= 0 )
top--;
Stack[top++] = i;
}
}
//旋转卡壳,求两点间距离平方的最大值
int rotating_calipers(Point p[],int n)
{
int ans = 0;
Point v;
int cur = 1;
for(int i = 0;i < n;i++)
{
v = p[i]-p[(i+1)%n];
while((v^(p[(cur+1)%n]-p[cur])) < 0)
cur = (cur+1)%n;
//printf("%d %d\n",i,cur);
ans = max(ans,max(dist2(p[i],p[cur]),dist2(p[(i+1)%n],p[(cur+1)%n])));
}
return ans;
}
Point p[MAXN];
int main()
{
int n;
while(scanf("%d",&n) == 1)
{
for(int i = 0;i < n;i++)
list[i].input();
Graham(n);
for(int i = 0;i < top;i++)
p[i] = list[Stack[i]];
printf("%d\n",rotating_calipers(p,top));
}
return 0;
}

未解决的问题

文章目录
  1. 1. 最近点对
    1. 1.1. ac code
  2. 2. 最远点对
    1. 2.1. ac code
  3. 3. 未解决的问题
{{ live2d() }}