BOJ 2261 - 가장 가까운 두 점
- x, y 좌표의 절댓값이 10000 이하인 점 N개가 주어진다.(여러 점이 같은 좌표를 가질 수도 있다) 이때 가장 가까운 두 점의 거리의 제곱을 출력하면 된다.(이 이후부터 거리의 제곱을 거리라 하겠다.)
문제 풀이
-
점들의 배열 ps에 대해서
int closest(int a, int b)함수를 ps의 a번째 점부터 b번째 점까지의 영역에서 가장 가까운 두 점의 거리를 출력하는 함수라 정의하자. 물론 ps는 점들의 x 좌표 기준으로 정렬되어 있어야 한다. mid=(a+b)/2로 정의하면 우선 [a, mid], [mid+1, b] 영역의 가장 가까운 두 점의 거리(ld, rd)를 각각 재귀로 구한다. -
ld, rd 중 작은 거리를 d로 저장하고 x 좌표가 [mid.x-d, mid.x+d]에 속하는 점들을 indAsx에 저장한다. indAsx의 점들을 y 좌표 기준으로 정렬 후에 indAsx의 점간의 거리를 하나하나 비교하며 d보다 작을 경우 d를 갱신한다.
-
indAsx의 i번째 점에 대해서 j=i+1번째 점부터 시작하는데, 이때 같은 좌표에 점이 몰려있으면 O(N^2)가 될 수 있기 때문에 만약 i, j번째 점의 y좌표의 거리가 d 이상이면 i를 넘긴다.(y좌표 순으로 정렬되어있기 때문에 j 이후의 점들은 모두 i와의 y좌표의 거리가 d 이상이기 때문)
소스코드
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
// closest, 88ms
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
int mid(int s, int e){return (s+e)>>1;}
int dist(pii a, pii b){
return pow(a.first-b.first, 2)+pow(a.second-b.second, 2);
// return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
bool comparey(pii a, pii b);
int paramsearch(vector<pii>& p, int l, int r, int piv, int d, int ord);
int closest(vector<pii>& p, int s, int e);
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
vector<pii> p(n);
for(auto& i:p){
int x, y;
cin>>x>>y;
i={x, y};
}
sort(p.begin(), p.end());
cout<<closest(p, 0, n-1);
}
bool comparey(pii a, pii b){
if(a.second==b.second) return a.first<b.first;
return a.second<b.second;
}
int paramsearch(vector<pii>& p, int l, int r, int piv, int d, int ord){//1:left, 0:right
while(l<=r){
int m=mid(l, r), md;
md=p[m].first-p[piv].first;
md*=md;
if(md>d){
if(ord) l=m+1;
else r=m-1;
}
else{
if(ord) r=m-1;
else l=m+1;
}
}
return l-1;
}
int closest(vector<pii>& p, int s, int e){
if(s==e) return 800000001;
if(e-s==1) return dist(p[s], p[e]);
int d1, d2, d=800000001;
d1=closest(p, s, mid(s, e));
d2=closest(p, mid(s, e)+1, e);
if(d1<d2) d=d1;
else d=d2;
d1=paramsearch(p, s, mid(s, e)-1, mid(s, e), d, 1);
d2=paramsearch(p, mid(s, e)+1, e, mid(s, e), d, 0);
if(d1==s-1) d1++;
vector<pii> ind;
for(int i=d1;i<=d2;i++) ind.push_back(p[i]);
sort(ind.begin(), ind.end(), comparey);
for(int i=0;i<ind.size()-1;i++) for(int j=i+1;j<ind.size();j++){
int ydiff=ind[j].second-ind[i].second;
ydiff*=ydiff;
if(ydiff>=d) break;
ydiff=dist(ind[i], ind[j]);
if(ydiff<d) d=ydiff;
}
return d;
}
풀고나서
- 내가 제출한 코드들 흐름
- 처음에는 indAsx를 [s, e]를 돌면서 추가함 -> O(N)
- parametric search를 이용해서 indAsx의 시작/끝 인덱스를 구하고 그 부분만 바로 추가시킴 -> O(logN)
- closesty를 정의해 closest와 같은 방법으로 d’를 구하고 y좌표 기준 +-d’를 N^2 비교 -> 결과적으로 재귀호출 비용이 증가해서 시간이 더 걸리게됨(아래 코드 참고)
- closesty를 추가한 이유 : x 좌표 기준 [mid.x-d, mid.x+d]의 영역에 점이 많을 경우에 N^2가 비효율적인 것 같았음
closesty 코드
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
// closesty, 108ms
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
int mid(int s, int e){return (s+e)>>1;}
int dist(pii a, pii b){return pow(a.first-b.first, 2)+pow(a.second-b.second, 2);}
bool comparey(pii a, pii b);
int paramsearch(vector<pii>& p, int l, int r, int piv, int d, int ord);
int closest(vector<pii>& p, int s, int e);
int closesty(vector<pii>& ind, int s, int e);
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
vector<pii> p(n);
for(auto& i:p){
int x, y;
cin>>x>>y;
i={x, y};
}
sort(p.begin(), p.end());
cout<<closest(p, 0, n-1);
}
bool comparey(pii a, pii b){
if(a.second==b.second) return a.first<b.first;
return a.second<b.second;
}
int paramsearch(vector<pii>& p, int l, int r, int piv, int d, int ord, int xy){//1:left, 0:right
while(l<=r){
int m=mid(l, r), md;
if(xy) md=p[m].first-p[piv].first;
else md=p[m].second-p[piv].second;
md*=md;
if(md>d){
if(ord) l=m+1;
else r=m-1;
}
else{
if(ord) r=m-1;
else l=m+1;
}
}
return l-1;
}
int closest(vector<pii>& p, int s, int e){
if(s==e) return 800000001;
if(e-s==1) return dist(p[s], p[e]);
int d1, d2, d;
d1=closest(p, s, mid(s, e));
d2=closest(p, mid(s, e)+1, e);
if(d1<d2) d=d1;
else d=d2;
d1=paramsearch(p, s, mid(s, e)-1, mid(s, e), d, 1, 1);
d2=paramsearch(p, mid(s, e)+1, e, mid(s, e), d, 0, 1);
if(d1==s-1) d1++;
vector<pii> ind;
for(int i=d1;i<=d2;i++) ind.push_back(p[i]);
sort(ind.begin(), ind.end(), comparey);
if(ind.size()<4){
for(int i=0;i<ind.size()-1;i++) for(int j=i+1;j<ind.size();j++){
int ydiff=ind[j].second-ind[i].second;
ydiff*=ydiff;
if(ydiff>=d) break;
ydiff=dist(ind[i], ind[j]);
if(ydiff<d) d=ydiff;
}
return d;
}
else{
int yd=closesty(ind, 0, ind.size()-1);
if(yd<d) return yd;
else return d;
}
}
int closesty(vector<pii>& ind, int s, int e){
if(s==e) return 800000001;
if(e-s==1) return dist(ind[s], ind[e]);
int d1, d2, d;
d1=closesty(ind, s, mid(s, e));
d2=closesty(ind, mid(s, e)+1, e);
if(d1<d2) d=d1;
else d=d2;
if(d==0) return 0;
d1=paramsearch(ind, s, mid(s, e)-1, mid(s, e), d, 1, 0);
d2=paramsearch(ind, mid(s, e)+1, e, mid(s, e), d, 0, 0);
if(d1==s-1) d1++;
for(int i=d1;i<d2;i++) for(int j=i+1;j<=d2;j++){
if(d<(ind[j].first-ind[i].first)*(ind[j].first-ind[i].first)) break;
int xd=dist(ind[i], ind[j]);
if(xd<d) d=xd;
}
return d;
}
- 분명히 closesty를 추가하면 시간이 줄어들어야 맞는데, 시간이 늘어난 이유를 모르겠다. 함수호출이 급격하게 증가해서 그런 것같아 indAsx의 개수가 4개 이하면 closesty를 호출하지 않고 바로 N^2비교를 하게 설정해서 10ms를 줄였지만 여전히 closest만 사용했을 때보다 20ms가 느리다.
Leave a comment