Minimum Sum(分治)
题意：
现在有 n n n 个向量， v i = ( x i , y i ) v_i = (x_i,y_i) vi=(xi,yi)
- v i 1 = ( x i , y i ) v_i^1 = (x_i, y_i) vi1=(xi,yi)
- v i 2 = ( − x i , y i ) v_i^2 = (-x_i, y_i) vi2=(−xi,yi)
- v i 3 = ( x i , − y i ) v_i^3 = (x_i,-y_i) vi3=(xi,−yi)
- v i 4 = ( − x i , − y i ) v_i^4=(-x_i,-y_i) vi4=(−xi,−yi)
求 m i n { ∣ v i k 1 + v j k 2 ∣ } min\{|v_i^{k1} + v_j^{k2}|\} min{∣vik1+vjk2∣}
思路：
向量和 转换成 两点间的距离。最后答案只需要点对的对第二个点全部取负，即 1 1 1 <-> 4 4 4 ， 2 2 2 <-> 3 3 3 。
每个点可以分成四个点，记录一下原来的序号和对应的指数，在分治比较时，相同序号的点不要比较即可。
这里分治时，当前区间的最小距离和答案的最小距离要分开更新，不然前者更新的时候有可能会覆盖掉后者更新过的答案。惨痛的经历。
还有，这题要加上
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
M L E MLE MLE 了一晚上。。
代码：
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<algorithm>
#define fi first
#define se second
//#include<stdlib.h>
//#include <time.h>
//srand((unsigned)time(NULL));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
using namespace std;
const int N = 4e5 + 10;
int n;
int tp[N];
int dx[5] = {0, 1, -1, 1, -1};
int dy[5] = {0, 1, 1, -1, -1};
struct Point{
int x, y;
int id, k;
Point() {}
Point(int _x, int _y) {
x = _x; y = _y;
}
}p[N];
bool cmp1(const Point& a, const Point& b) {
if (a.x == b.x) return a.y < b.y;
else return a.x < b.x;
}
bool cmp2(const int& a, const int& b) {
return p[a].y < p[b].y;
}
int dist(int i, int j) {
int xx = p[i].x - p[j].x;
int yy = p[i].y - p[j].y;
return xx * xx + yy * yy;
}
int ans_i, ans_j;
int ans_k1, ans_k2;
int min_dis;
int Merge(int l, int r) {
int d = INF;
if (l == r) return d;
int mid = (l + r) >> 1;
int d1 = Merge(l, mid);
int d2 = Merge(mid + 1, r);
d = min(d1, d2);
min_dis = min(min_dis, d);
int k = 0;
for (int i = l; i <= r; i++) {
if (mid != i && p[mid].id == p[i].id) continue;
int len = abs(p[mid].x - p[i].x);
if (len * len < d) tp[++k] = i;
}
sort(tp + 1, tp + 1 + k, cmp2);
for (int i = 1; i <= k; i++) {
for (int j = i + 1; j <= k; j++) {
if (p[tp[j]].id == p[tp[i]].id) continue;
int len = p[tp[j]].y - p[tp[i]].y;
if (len * len >= d) break;
int d3 = dist(tp[i], tp[j]);
if (d3 < min_dis) {
min_dis = d3;
ans_i = p[tp[j]].id; ans_k1 = p[tp[j]].k;
ans_j = p[tp[i]].id; ans_k2 = p[tp[i]].k;
}
if (d3 < d) d = d3;
}
}
return d;
}
int change(int x) {
if (x == 1) return 4;
else if (x == 2) return 3;
else if (x == 3) return 2;
else return 1;
}
int main() {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d%d", &x, &y);
p[i].x = x; p[i].y = y;
p[i].id = i; p[i].k = 1;
}
int cnt = n;
for (int i = 1; i <= cnt; i++) {
for (int j = 2; j <= 4; j++) {
++n;
p[n].id = i; p[n].k = j;
p[n].x = p[i].x * dx[j];
p[n].y = p[i].y * dy[j];
}
}
sort(p + 1, p + 1 + n, cmp1);
min_dis = INF;
Merge(1, n);
ans_k2 = change(ans_k2);
// printf("%lld\n", mmin);
printf("%d %d %d %d\n", ans_i, ans_k1, ans_j, ans_k2);
return 0;
}