前不久点对,总括几何の近期点对

Sample Input

View Code

 

 

2
4
0 0
0 1
1 0
1 1
2 2
2 3
3 2
3 3
4
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

思路2:暴力枚举+剪枝。暴力枚举每多个点时期的离开,若y[j] – y[i]
>= mind则break(这么些毫无解释了吧……)

1.414
0.000

图片 1图片 2

 

After successive failures in the battles against the Union, the Empire
retreated to its last stronghold. Depending on its powerful defense
system, the Empire repelled the six waves of Union’s attack. After
several sleepless nights of thinking, Arthur, General of the Union,
noticed that the only weakness of the defense system was its energy
supply. The system was charged by N nuclear power stations and
breaking down any of them would disable the system.

 

 1 void gen1()
 2 {
 3     int N = 30000, i;
 4     printf("%d\n", N);
 5     for( i = 0; i < N; ++i )
 6         printf("%d %d\n", -999199789+i, i+113);
 7     for( i = 0; i < N; ++i )
 8         printf("%d %d\n", 999199987+i, i+113);
 9 
10     printf("%d\n", N);
11     for( i = 0; i < N; ++i )
12         printf("%d %d\n", i-1024, -999269789+i);
13     for( i = 0; i < N; ++i )
14         printf("%d %d\n", i-1024, 995499987+i);
15 }

For each test case output the minimum distance with precision of three
decimal placed in a separate line.

分治算法:1141MS

难点叙述:

图片 3图片 4

Input

然后外人给的代码,待商讨,出处不明……某份数据依旧要四秒之多,然则假如用地方小编的代码直接就不会动了……

  据悉数据相比水能够暴力

标题马虎:给多个点集A,三个点集B,求min(distance(x, y))(x∈A,y∈B)

The first line is a integer T representing the number of test cases.
Each test case begins with an integer N (1 ≤ N ≤ 100000).
The next N lines describe the positions of the stations. Each line
consists of two integers X (0 ≤ X ≤ 1000000000) and Y (0 ≤ Y ≤
1000000000) indicating the positions of the station.
The next following N lines describe the positions of the agents. Each
line consists of two integers X (0 ≤ X ≤ 1000000000) and Y (0
≤ Y ≤ 1000000000) indicating the positions of the agent.  

 

Description

开始估价,上边包车型地铁代码应用了10分啥K-D
tree,正是把三个2维空间先分x轴、再分y轴、再分x轴、再分y轴……分成多少个平面,而不是像上边那样只分x(或y)轴……然后依旧分治……代码小编就懒得看了……超出作者的品位上限了……

Sample Output

Input

 

View Code

Output

思路一:分治法。把点集按x坐标从小到大排序,mid = (left +
right)/二,递归分治总结出左手部分和右手部分的微乎其微距离mind,那么,若左半有的和右半部分存在一对点偏离小于mind,那么那多个点一定在限定(x[mid]
-mind ,x[mid]
-mind)之间(因为在那之外的点与对面包车型大巴点的离开必然当先mind)

  http://poj.org/problem?id=3714

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <queue>
  5 #include <iostream>
  6 #include <cmath>
  7 
  8 using namespace std;
  9 
 10 //维数
 11 int K = 2;
 12 long long ans;
 13 
 14 struct kdNode
 15 {
 16     long long x[2];
 17     int div;
 18 };
 19 
 20 struct qNode
 21 {
 22     long long r;
 23     kdNode p;
 24     qNode( long long _r, kdNode _p )
 25     {
 26         r = _r;
 27         p = _p;
 28     }
 29     bool operator<( const qNode& x ) const
 30     {
 31         return r < x.r;
 32     }
 33 };
 34 
 35 int cmpNo;
 36 int cmp( kdNode a, kdNode b )
 37 {
 38     return a.x[cmpNo] < b.x[cmpNo];
 39 }
 40 
 41 long long dis2( kdNode& a, kdNode& b )
 42 {
 43     long long res = 0;
 44     for( int i = 0; i < K; ++i )
 45         res += (a.x[i]-b.x[i])*(a.x[i]-b.x[i]);
 46     return res;
 47 }
 48 
 49 void buildKD( int s, int e, kdNode* p, int d )
 50 {
 51     if( s > e )    return;
 52     int mid = (s+e)/2;
 53     cmpNo = d;
 54     nth_element(p+s, p+mid, p+e+1, cmp);
 55     p[mid].div = d;
 56     buildKD(s, mid-1, p, (d+1)%K);
 57     buildKD(mid+1, e, p, (d+1)%K);
 58 }
 59 
 60 priority_queue<qNode> Q;
 61 
 62 void findKD( int s, int e, kdNode tar, kdNode* p, int cnt )
 63 {
 64     if( s > e )    return;
 65     int mid = (s+e)/2;
 66     long long r = dis2(p[mid], tar);
 67     ans = min(ans, r);
 68     //t也许需要改成long long
 69     long long t = tar.x[ p[mid].div ] - p[mid].x[ p[mid].div ];
 70     if( t <= 0 )
 71     {
 72         findKD(s, mid-1, tar, p, cnt);
 73         if( ans > t*t )
 74             findKD(mid+1, e, tar, p, cnt);
 75     }
 76     else if( t > 0 )
 77     {
 78         findKD(mid+1, e, tar, p, cnt);
 79         if( ans > t*t )
 80             findKD(s, mid-1, tar, p, cnt);
 81     }
 82 }
 83 
 84 kdNode p[50010], q;
 85 
 86 int main()
 87 {
 88     //freopen("data.in", "r", stdin);
 89     //freopen("data.out", "w", stdout);
 90     int T, n, i, j;
 91     int x, y;
 92     scanf("%d", &T);
 93     while( T-- )
 94     {
 95         scanf("%d", &n);
 96         for( i = 0; i < n; ++i )
 97         {
 98             scanf("%d %d", &x, &y);
 99             p[i].x[0] = x;
100             p[i].x[1] = y;
101         }
102         ans = 4100000000000000000LL;
103         buildKD(0, n-1, p, K-1);
104         for( i = 0; i < n; ++i )
105         {
106             scanf("%d %d", &x, &y);
107             q.x[0] = x;
108             q.x[1] = y;
109             findKD(0, n-1, q, p, 1);
110         }
111         printf("%.3f\n", sqrt(ans+0.));
112     }
113     return 0;
114 }

难题链接:

 

  注意会爆int

The general soon started a raid to the stations by N special agents
who were paradroped into the stronghold. Unfortunately they failed to
land at the expected positions due to the attack by the Empire Air
Force. As an experienced general, Arthur soon realized that he needed to
rearrange the plan. The first thing he wants to know now is that which
agent is the nearest to any power station. Could you, the chief officer,
help the general to calculate the minimum distance between an agent and
a station?

After successive failures in the battles against the Union, the Empire
retreated to its last stronghold. Depending on its powerful defense
system, the Empire repelled the six waves of Union’s attack. After
several sleepless nights of thinking, Arthur, General of the Union,
noticed that the only weakness of the defense system was its energy
supply. The system was charged by N nuclear power stations and
breaking down any of them would disable the system.

图片 5图片 6

思路:

Description

Raid

View Code

  有多个点集,求集合差别的点的微小距离

The first line is a integer T representing the number of test cases.
Each test case begins with an integer N (1 ≤ N ≤ 100000).
The next N lines describe the positions of the stations. Each line
consists of two integers X (0 ≤ X ≤ 1000000000) and Y (0 ≤ Y ≤
1000000000) indicating the positions of the station.
The next following N lines describe the positions of the agents. Each
line consists of two integers X (0 ≤ X ≤ 1000000000) and Y (0
≤ Y ≤ 1000000000) indicating the positions of the agent. 

The general soon started a raid to the stations by N special agents
who were paradroped into the stronghold. Unfortunately they failed to
land at the expected positions due to the attack by the Empire Air
Force. As an experienced general, Arthur soon realized that he needed to
rearrange the plan. The first thing he wants to know now is that which
agent is the nearest to any power station. Could you, the chief officer,
help the general to calculate the minimum distance between an agent and
a station?

 分治算法:14八伍MS

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 
10 const LL INF = 1000000000000;
11 const int N = 100010;
12 
13 struct Node {
14     LL x, y;
15     int id;
16     Node(LL x = 0, LL y = 0, int id = 0) :x(x), y(y), id(id) {}
17     const bool operator < (const Node A) const {
18         return x == A.x ? y < A.y : x < A.x;
19     }
20 }no[2 * N];
21 
22 int n;
23 
24 double dis(int a, int b) {
25     return sqrt((double)((no[a].x - no[b].x)*(no[a].x - no[b].x) + (no[a].y - no[b].y)*(no[a].y - no[b].y)));
26 }
27 
28 double solve(int l, int r) {
29     if (l == r)return INF;
30     int mid = (l + r) >> 1;
31     double a = solve(l, mid);
32     double b = solve(mid + 1, r);
33     double d = min(a, b);
34     for (int i = mid; i >= l; --i) {
35         if (no[mid].x - no[i].x > d)break;
36         for (int j = mid + 1; j <= r; ++j) {
37             if (no[j].x - no[i].x > d)break;
38             double tmp = dis(i, j);
39             if (no[i].id != no[j].id&&tmp < d)d = tmp;
40         }
41     }
42     return d;
43 }
44 
45 int main() {
46     int t;
47     scanf("%d", &t);
48     while (t--) {
49         scanf("%d", &n);
50         for (int i = 0; i < n; ++i) {
51             scanf("%lld%lld", &no[i].x, &no[i].y);
52             no[i].id = 1;
53         }
54         for (int i = 0; i < n; ++i) {
55             scanf("%lld%lld", &no[i + n].x, &no[i + n].y);
56             no[i + n].id = 2;
57         }
58         sort(no, no + 2 * n);
59         double ans = solve(0, 2 * n - 1);
60         printf("%.3lf\n", ans);
61     }
62 }
 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const double MAX_DIST = 1e100;
 7 const int MAXN = 200010;
 8 
 9 struct Point {
10     double x, y;
11     bool flag;
12 };
13 
14 inline double dist(const Point &a, const Point &b) {
15     if(a.flag != b.flag)
16         return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
17     else
18         return MAX_DIST;
19 }
20 
21 Point pt[MAXN];
22 int y_sort[MAXN];
23 
24 inline bool x_cmp(const Point &a, const Point &b) {
25     return a.x < b.x;
26 }
27 
28 inline bool y_cmp(const int &a, const int &b) {
29     return pt[a].y < pt[b].y;
30 }
31 
32 double shortest_distance(int left, int right) {
33     if(right - left == 1)
34         return dist(pt[left], pt[right]);
35     else if(right - left == 2)
36         return min(min(dist(pt[left], pt[left+1]), dist(pt[left], pt[left+2])),
37                         dist(pt[left+1], pt[left+2]));
38     int mid = (left + right) >> 1;
39     double mind = min(shortest_distance(left, mid), shortest_distance(mid+1, right));
40     if(mind == 0) return 0;
41     int yn = 0;
42     for(int i = mid; pt[mid].x - pt[i].x < mind && i >= left; --i)
43         y_sort[yn++] = i;
44     int y_mid = yn;
45     for(int i = mid+1; pt[i].x - pt[mid].x < mind && i <= right; ++i)
46         y_sort[yn++] = i;
47     for(int i = 0; i < y_mid; ++i) for(int j = y_mid; j < yn; ++j)
48         mind = min(mind, dist(pt[y_sort[i]], pt[y_sort[j]]));
49     return mind;
50 }
51 
52 int main() {
53     int T;
54     scanf("%d", &T);
55     while(T--) {
56         int n;
57         scanf("%d", &n);
58         for(int i = 0; i < n; ++i) {
59             scanf("%lf%lf", &pt[i].x, &pt[i].y);
60             pt[i].flag = false;
61         }
62         for(int i = n; i < 2*n; ++i) {
63             scanf("%lf%lf", &pt[i].x, &pt[i].y);
64             pt[i].flag = true;
65         }
66         sort(pt, pt + 2*n, x_cmp);
67         printf("%.3f\n", shortest_distance(0, 2 * n - 1));
68     }
69 }

  分治,和经典近期点对同一,以x坐标排序,划中线分成两堆,递归求每堆的近来距离d,然后对两堆之间横坐标为
x[mid] – d 和 x[mid] + d 之间的点暴力看是否有比 d
小的偏离

PS:要封存四个人小数,标题没说,能够看样例

代码:

View Code

标题大意:

图片 7图片 8

暴力枚举+剪枝:十3二MS

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const double MAX_DIST = 1e100;
const int MAXN = 200010;

struct Point {
    double x, y;
    bool flag;
};

inline double dist(const Point &a, const Point &b) {
    if(a.flag != b.flag)
        return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    else
        return MAX_DIST;
}

Point pt[MAXN];
int y_sort[MAXN];

inline bool x_cmp(const Point &a, const Point &b) {
    return a.x < b.x;
}

inline bool y_cmp(const int &a, const int &b) {
    return pt[a].y < pt[b].y;
}

void _min(double &a, const double &b) {
    if(a > b) a = b;
}

double shortest_distance(int left, int right) {
    if(right - left == 1)
        return dist(pt[left], pt[right]);
    else if(right - left == 2)
        return min(min(dist(pt[left], pt[left+1]), dist(pt[left], pt[left+2])),
                        dist(pt[left+1], pt[left+2]));
    int mid = (left + right) >> 1;
    double mind = min(shortest_distance(left, mid), shortest_distance(mid+1, right));
    if(mind == 0) return 0;
    int yn = 0;
    for(int i = mid; pt[mid].x - pt[i].x < mind && i >= left; --i)
        y_sort[yn++] = i;
    for(int i = mid+1; pt[i].x - pt[mid].x < mind && i <= right; ++i)
        y_sort[yn++] = i;
    sort(y_sort, y_sort + yn);
    for(int i = 0; i < yn; ++i) {
        for(int j = i + 1; j < yn; ++j) {
            if(pt[y_sort[j]].y - pt[y_sort[i]].y >= mind) break;
            _min(mind, dist(pt[y_sort[i]], pt[y_sort[j]]));
        }
    }
    return mind;
}

int main() {
    freopen("f:/data.in", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%lf%lf", &pt[i].x, &pt[i].y);
            pt[i].flag = false;
        }
        for(int i = n; i < 2*n; ++i) {
            scanf("%lf%lf", &pt[i].x, &pt[i].y);
            pt[i].flag = true;
        }
        sort(pt, pt + 2*n, x_cmp);
        printf("%.3f\n", shortest_distance(0, 2 * n - 1));
    }
}
 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int MAXN = 200010;
 7 
 8 struct Point {
 9     double x, y;
10     bool flag;
11 };
12 
13 inline double dist(const Point &a, const Point &b) {
14     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
15 }
16 
17 Point pt[MAXN];
18 
19 inline bool cmp(const Point &a, const Point &b) {
20     if(a.x == b.x) return a.y < b.y;
21     return a.x < b.x;
22 }
23 
24 double shortest_distance(int pn) {
25     double mind = dist(pt[0], pt[pn/2]);
26     sort(pt, pt + pn, cmp);
27     for(int i = 0; i < pn; ++i) {
28         for(int j = i + 1; j < pn; ++j) {
29             if(pt[i].flag == pt[j].flag) continue;
30             double t = dist(pt[i], pt[j]);
31             if(mind > t) mind = t;
32             if(pt[j].x - pt[i].x >= mind) break;
33         }
34     }
35     return mind;
36 }
37 
38 int main() {
39     int T;
40     scanf("%d", &T);
41     while(T--) {
42         int n;
43         scanf("%d", &n);
44         for(int i = 0; i < n; ++i) {
45             scanf("%lf%lf", &pt[i].x, &pt[i].y);
46             pt[i].flag = false;
47         }
48         for(int i = n; i < 2*n; ++i) {
49             scanf("%lf%lf", &pt[i].x, &pt[i].y);
50             pt[i].flag = true;
51         }
52         printf("%.3f\n", shortest_distance(2 * n));
53     }
54 }

后记:那分治法能卡(暴力剪枝肯定能卡……),上面是生成卡分治数据的代码……

 

View Code

 

图片 9图片 10