-
Notifications
You must be signed in to change notification settings - Fork 0
/
closest-pair.cpp
121 lines (109 loc) · 3.39 KB
/
closest-pair.cpp
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
114
115
116
117
118
119
120
121
/*
** Vishal Raj Roy
** Indian Institute of Technology Kharagpur
*/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define um(A,B) unordered_map <A, B>
#define us(A) unordered_set <A>
#define ms(A) multiset <A>
#define all(x) x.begin(),x.end()
#define ins insert
#define xx first
#define yy second
#define sz(x) ((int)x.size())
#define count_ones __builtin_popcountl
#define watch(x) cout << (#x) << " is " << (x) << endl
#define sqr(x) ((x)*(x))
#define mod(x, m) ((((x) % (m)) + (m)) % (m))
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mem(x,val) memset((x),(val),sizeof(x));
#define rite(X) freopen("X.txt","w",stdout);
#define read(X) freopen("X.txt","r",stdin);
#define FOR(i,A,B) for( auto (i) = (A); (i) < (B); (i)++ )
#define FORN(i,A,B) for( auto (i) = (B); (i) >= (A); (i)-- )
#define ima INT_MAX
#define imi INT_MIN
#define lma LLONG_MAX
#define lmi LLONG_MIN
typedef long long int li;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef unordered_map<int,int> umii;
typedef unordered_map<string,int> umsi;
typedef unordered_set<string> uss;
typedef unordered_set<int> usi;
typedef unordered_set<int, usi> usii;
typedef multiset<int> msi;
typedef multiset<string> mss;
typedef pair<li, li> ll;
typedef pair<li, ll> lll;
typedef vector<li> vl;
typedef vector<ll> vll;
typedef vector<lll> vlll;
typedef vector<vl> vvl;
typedef unordered_map<li,li> umll;
typedef unordered_map<string,li> umsl;
typedef unordered_set<string> uss;
typedef unordered_set<li> usl;
typedef unordered_set<li, usl> usll;
typedef multiset<li> msl;
typedef multiset<string> mss;
const double pi = 2 * acos(0.0);
const int oo = 0x3f3f3f3f; // don't use for long long
const double inf = 1.0/0.0;
int mindist = ima; pair<ii,ii> bestpoint;
vii t;
bool c_x( ii a, ii b ) {
return a.xx < b.xx || (a.xx == b.xx && a.yy < b.yy );
}
bool c_y( ii a, ii b ) {
return a.yy < b.yy;
}
void update( ii p1, ii p2 ) {
int d = sqr(p1.xx-p2.xx)+sqr(p1.yy-p2.yy);
if( d < mindist ) {
mindist = d; bestpoint = {p1,p2};
}
}
void closestpair( vii A, int l, int r ) {
if( r-l <= 3 ) {
sort(A.begin()+l,A.begin()+r,c_y);
FOR(i,l,r)
FOR(j,i+1,r)
update(A[i],A[j]);
return;
}
int mid = (l+r) >> 1;
ii midp = A[mid];
closestpair(A,l,mid); closestpair(A,mid,r);
merge(A.begin()+l, A.begin()+mid, A.begin()+mid, A.begin()+r, t.begin(), c_y);
copy(t.begin(),t.begin()+r-l,A.begin()+l);
int k = 0;
FOR(i,l,r)
if( sqr(midp.xx-A[i].xx) < mindist ) {
for( int j = k-1; j >= 0 && sqr(A[i].yy-t[j].yy) < mindist; j-- ) update(A[i],t[j]);
t[k++] = A[i];
}
}
int main() {
ios_base::sync_with_stdio(0);
//vii A{{15,2},{7,2},{5,2},{1,2},{30,2},{16,16},{32,35},{45,32}};
vii A{{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
sort(A.begin(), A.end(), c_x);
t.resize(sz(A));
closestpair(A,0,sz(A));
cout<<sqrt(mindist)<<"dddddd\n";
cout<< bestpoint.xx.xx <<" "<< bestpoint.xx.yy<<" "<< bestpoint.yy.xx<<" "<< bestpoint.yy.yy<<"\n";
return 0;
}