本文共 7511 字，大约阅读时间需要 25 分钟。
hdu 1007 Quoit Design 最近点模板题目
题意：
给你n个点求平面上任意两点的最短距离
思路：
平面最近点对距离模板题，见算法导论P591
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define keyTree (chd[chd[root][1]][0])#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 100007#define N 100007using namespace std;int dx[4]={-1,1,0,0};int dy[4]={ 0,0,-1,1};const int inf = 0x7f7f7f7f;const int mod = 1000000007;const double eps = 1e-8;struct Point{ double x,y;}pt[N];int a[N];int n;int cmp(Point a, Point b){ if (a.x != b.x) return a.x < b.x; else return a.y < b.y;}int cmp_y(int a,int b){ return pt[a].y < pt[b].y;}double getDis(const Point &a, const Point &b){ double x = a.x - b.x; double y = a.y - b.y; return sqrt(x*x + y*y);}double solve(int l, int r){ double ans = 0; if (r - l + 1 <= 3) { if (r - l + 1 == 1) return ans; ans = getDis(pt[l], pt[l + 1]); if (r - l + 1 == 2) return ans; for (int i = l; i < r; ++i) { for (int j = i + 1; j <= r; ++j) { ans = min(ans, getDis(pt[i],pt[j])); } } return ans; } int m = (l + r) >> 1; double s1 = solve(l, m); double s2 = solve(m + 1, r); ans = min(s1,s2); int k = 0; for (int i = m - 1; i >= l && pt[m].x - pt[i].x <= ans; --i) a[k++] = i; for (int i = m + 1; i <= r && pt[i].x - pt[m].x <= ans; ++i) a[k++] = i; //sort(a, a + k, cmp_y); for (int i = 0; i < k; ++i) { for (int j = i + 1; j < k && j <= i + 7; ++j) { ans = min(ans, getDis(pt[a[i]], pt[a[j]])); } } return ans;}int main(){ while (~scanf("%d",&n)) { if (!n) break; for (int i = 0; i < n; ++i) scanf("%lf%lf",&pt[i].x, &pt[i].y); sort(pt, pt + n, cmp); printf("%.2lf\n",solve(0, n - 1)/2.0); } return 0;}
Pku 3714 Raid
给你n个A种点，n个B种点，求A种点中距离B种点最近的距离
还是平面最近点对模板的加强，就是判断一下只有点的种类不同才能计算距离
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define keyTree (chd[chd[root][1]][0])#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 100007#define N 100007using namespace std;int dx[4]={-1,1,0,0};int dy[4]={ 0,0,-1,1};const double inf = 100000000000.0;const int mod = 1000000007;const double eps = 1e-8;struct Point{ double x,y; int id;}pt[2*N];int a[2*N];int n;int cmp(Point a, Point b){ if (a.x != b.x) return a.x < b.x; else return a.y < b.y;}int cmp_y(int a,int b){ return pt[a].y < pt[b].y;}double getDis(const Point &a, const Point &b){ if (a.id == b.id) return inf; double x = a.x - b.x; double y = a.y - b.y; return sqrt(x*x + y*y);}double solve(int l, int r){ double ans = inf; if (r - l + 1 <= 3) { for (int i = l; i < r; ++i) { for (int j = i + 1; j <= r; ++j) { if (pt[i].id != pt[j].id) ans = min(ans, getDis(pt[i], pt[j])); } } return ans; } int m = (l + r) >> 1; double s1 = solve(l, m); double s2 = solve(m, r); ans = min(s1,s2); int k = 0; for (int i = m - 1; i >= l && pt[m].x - pt[i].x <= ans; --i) a[k++] = i; for (int i = m + 1; i <= r && pt[i].x - pt[m].x <= ans; ++i) a[k++] = i; sort(a, a + k, cmp_y); for (int i = 0; i < k; ++i) { for (int j = i + 1; j < k && j <= i + 7; ++j) { if (pt[a[i]].id != pt[a[j]].id) ans = min(ans, getDis(pt[a[i]], pt[a[j]])); } } return ans;}int main(){ int T; scanf("%d",&T); while (T--) { scanf("%d",&n); for (int i = 0; i < n; ++i) scanf("%lf%lf",&pt[i].x, &pt[i].y), pt[i].id = 0; for (int i = n; i < 2*n; ++i) scanf("%lf%lf",&pt[i].x, &pt[i].y), pt[i].id = 1; n *= 2; sort(pt, pt + n, cmp); printf("%.3lf\n",solve(0, n - 1)); } return 0;}
hdu 4631 Sad Love Story
向一个空的平面上加点，每次加入一点求该平面里面最近点对之间的距离的平方为s[i]，求s[2] + s[3] + s[n]d的总和
贪心+最近点对
首先我们求出整个平面加完n个点之后的最近点对i,j，pt[i].id表示i是第几个加入的， 那么在max(pt[i].id, pt[j].id)之后的点加进来的话肯定也是这个值，这样我们就省去了一大段的计算，然后进行了优化。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define keyTree (chd[chd[root][1]][0])#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 100007#define N 500007using namespace std;int dx[4]={-1,1,0,0};int dy[4]={ 0,0,-1,1};const double inf = 100000000000.0;const int mod = 1000000007;struct Point{ int x,y; int id;}pt[N],p[N];int a[N];int n;int Ax,Bx,Cx,Ay,By,Cy;int cmp(const Point &a, const Point &b){ if (a.x != b.x) return a.x < b.x; else return a.y < b.y;}int cmp_y(int a, int b){ return pt[a].y < pt[b].y;}ll getDis(const Point &a, const Point &b){ ll x = a.x - b.x; ll y = a.y - b.y; return x*x + y*y;}ll MinDis(int l,int r,int &top){ int len = r - l + 1; ll s3; if (len <= 3) { s3 = getDis(pt[l],pt[l + 1]); top = max(pt[l].id, pt[l + 1].id); if (len == 2) return s3; else { ll tmp = getDis(pt[l],pt[l + 2]); if (s3 > tmp) { s3 = tmp; top = max(pt[l].id, pt[l + 2].id); } tmp = getDis(pt[l + 1], pt[l + 2]); if (s3 > tmp) { s3 = tmp; top = max(pt[l + 1].id, pt[l + 2].id); } } return s3; } int m = (l + r) >> 1; int top1, top2; ll s1 = MinDis(l, m, top1); ll s2 = MinDis(m, r, top2); if (s1 < s2) { s3 = s1, top = top1; } else if (s1 > s2){ s3 = s2, top = top2; } else { s3 = s1, top = min(top1, top2); } int k = 0; for (int i = m - 1; i >= l && pt[m].x - pt[i].x <= s3; --i) a[k++] = i; for (int i = m + 1; i <= r && pt[i].x - pt[m].x <= s3; ++i) a[k++] = i; sort(a, a + k, cmp_y); for (int i = 0; i < k; ++i) { for (int j = i + 1; j < k && j <= i + 7; ++j) { ll tmp = getDis(pt[a[i]], pt[a[j]]); if (s3 > tmp) { s3 = tmp; top = max(pt[a[i]].id,pt[a[j]].id); } } } return s3;}int main(){ int T; scanf("%d",&T); while (T--) { scanf("%d%d%d%d%d%d%d",&n,&Ax,&Bx,&Cx,&Ay,&By,&Cy); p[0].x = 0; p[0].y = 0; for (int i = 1; i <= n; ++i) { p[i].x = (ll)((ll)Ax*p[i - 1].x + Bx)%Cx; p[i].y = (ll)((ll)Ay*p[i - 1].y + By)%Cy; p[i].id = i; } ll sum = 0; while (n >= 2) { for (int i = 1; i <= n; ++i) pt[i] = p[i]; sort(pt + 1, pt + 1 + n, cmp); int top = 0; ll tmp = MinDis(1,n,top); sum += (tmp * (n - top + 1)); n = top - 1; } printf("%I64d\n",sum); } return 0;}
转载地址：http://chrdl.baihongyu.com/
