平面最近点对题目

时间:2021-02-23 09:27:59

hdu 1007 Quoit Design 最近点模板题目

题意:

给你n个点求平面上任意两点的最短距离

思路:

平面最近点对距离模板题,见算法导论P591

平面最近点对题目平面最近点对题目
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>


#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 100007

using 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;
}
View Code

 

Pku 3714 Raid 

题意:

给你n个A种点,n个B种点,求A种点中距离B种点最近的距离

思路:

还是平面最近点对模板的加强,就是判断一下只有点的种类不同才能计算距离

平面最近点对题目平面最近点对题目
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>


#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 100007

using 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;
}
View Code

 

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 <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>


#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 500007

using 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;
}
View Code