代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 struct Point 10 { 11 double m_x, m_y; 12 Point():m_x(0.0),m_y(0.0) {} 13 Point(double x, double y):m_x(x),m_y(y) {} 14 bool operator==(const Point& p) const 15 { 16 return m_x==p.m_x && m_y==p.m_y; 17 } 18 }; 19 20 ostream& operator<<(ostream& os, const Point& p) 21 { 22 return os <<"(" <"," <")"; 23 } 24 template<class T, class Pr> 25 void insert_sort(vector &vec, int l, int r, Pr pred) 26 { 27 int i, j; 28 for (i=l+1; i<=r; i++) 29 { 30 T tmp = vec[i]; 31 for (j=i-1; j>=l && pred(tmp,vec[j]); j--) 32 vec[j+1]=vec[j]; 33 vec[j+1] = tmp; 34 } 35 } 36 template<class T> 37 int get_position(vector &vec, int l, int r, T key) 38 { 39 for (int i=l; i<=r; i++) 40 if (key == vec[i]) 41 return i; 42 return -1; 43 } 44 template<class T, class Pr> 45 int partition(vector &vec, int l, int r, Pr pred) 46 { 47 int i, j; 48 for (i=l+1,j=l; i<=r; i++) 49 { 50 if (pred(vec[i],vec[l])) 51 { 52 ++j; 53 swap(vec[i],vec[j]); 54 } 55 } 56 swap(vec[j],vec[l]); 57 return j; 58 } 59 60 template<class T, class Pr> 61 T select(vector &vec, int l, int r, int k, Pr pred) 62 { 63 int n = r-l+1; 64 if (n==1) 65 { 66 if (k!=0) 67 printf("Out of Boundary!\n"); 68 return vec[l]; 69 } 70 int cnt = n/5; 71 int tcnt = (n+4)/5; 72 int rem = n%5; 73 vector group(tcnt); 74 int i, j; 75 for (i=0,j=l; i5) 76 { 77 insert_sort(vec, j, j+4, pred); 78 group[i] = vec[j+2]; 79 } 80 if (rem) 81 { 82 insert_sort(vec, j, j+rem-1, pred); 83 group[i] = vec[j+(rem-1)/2]; 84 } 85 T key = select(group, 0, tcnt-1, (tcnt-1)/2, pred); 86 87 int key_pos = get_position(vec, l, r, key); 88 swap(vec[key_pos], vec[l]); 89 int pos = partition(vec, l, r, pred); 90 int x = pos - l; 91 if (x == k) return key; 92 else if (x < k) 93 return select(vec, pos+1, r, k-x-1, pred); 94 else 95 return select(vec, l, pos-1, k, pred); 96 } 97 double dist(const Point& a, const Point& b) 98 { 99 double x = a.m_x-b.m_x; 100 double y = a.m_y-b.m_y; 101 return sqrt(x*x+y*y); 102 } 103 104 bool cmpX(const Point& a, const Point& b) 105 { 106 return a.m_x < b.m_x; 107 } 108 109 bool cmpY(const Point& a, const Point& b) 110 { 111 return a.m_y < b.m_y; 112 } 113 114 double minDifferent(vector p, int l, int r, vector &result) 115 { 116 if ((r-l+1)==2) 117 { 118 result[0] = p[l]; 119 result[1] = p[r]; 120 if (cmpX(p[r],p[l])) swap(p[l], p[r]); 121 return dist(p[l], p[r]); 122 } 123 if ((r-l+1)==3) 124 { 125 insert_sort(p, l, r, cmpX); 126 double tmp1 = dist(p[l], p[l+1]); 127 double tmp2 = dist(p[l+1], p[l+2]); 128 double ret = min(tmp1, tmp2); 129 if (tmp1 == ret) 130 { 131 result[0] = p[l]; 132 result[1] = p[l+1]; 133 } 134 else 135 { 136 result[0] = p[l+1]; 137 result[1] = p[l+2]; 138 } 139 return ret; 140 } 141 int mid = (r+l)>>1; 142 Point median = select(p, l, r, mid-l, cmpX); 143 vector res1(2), res2(2); 144 double min_l = minDifferent(p, l, mid, res1); 145 double min_r = minDifferent(p, mid+1, r, res2); 146 double minum = min(min_l, min_r); 147 if (minum == min_l) 148 { 149 result[0] = res1[0]; 150 result[1] = res1[1]; 151 } 152 else 153 { 154 result[0] = res2[0]; 155 result[1] = res2[1]; 156 } 157 vector yvec; 158 int i, j; 159 for (i=mid+1; i<=r; i++) 160 if (p[i].m_x - p[mid].m_x < minum) 161 yvec.push_back(Point(p[i])); 162 for (i=mid; i>=l; i--) 163 if (p[mid+1].m_x - p[i].m_x < minum) 164 yvec.push_back(Point(p[i])); 165 sort(yvec.begin(), yvec.end(), cmpY); 166 for (i=0; i) 167 { 168 for (j=i+1; j169 j<=i+7; j++) 170 { 171 double delta = dist(yvec[i],yvec[j]); 172 if (delta < minum) 173 { 174 minum = delta; 175 result[0] = yvec[i]; 176 result[1] = yvec[j]; 177 } 178 } 179 } 180 return minum; 181 } 182 183 int main() 184 { 185 int n, i, j; 186 double x, y; 187 int k = 0; 188 map<int,Point> m; 189 vector result(2); 190 vector input; 191 cin >> n; 192 for (i=0; i) 193 { 194 cin >> x; 195 cin >> y; 196 input.push_back(Point(x,y)); 197 m.insert(pair<int,Point>(k,Point(x,y))); 198 k++; 199 } 200 double minum = minDifferent(input, 0, input.size()-1, result); 201 202 for(map<int,Point>::iterator it = m.begin();it != m.end();it++) 203 { 204 if(it->secOnd== result[0]) 205 { 206 cout<first; 207 } 208 if(it->secOnd== result[1]) 209 { 210 cout<<" "<first; 211 } 212 } 213 214 215 return 0; 216 }
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号