• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# ander franz - gg ok

a guest May 22nd, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. #define min(a, b) ((a)<(b)?(a):(b))
6. #define MAX 9999.99999
7.
8. struct Point { double x, y; };
9. Point p[10001];
10.
11. double dist(Point p1, Point p2) {
12.     return hypot(p1.x - p2.x, p1.y - p2.y);
13. }
14.
15. int compare(const void *a, const void *b){
16.     Point *sp1 = (Point *)a;
17.     Point *sp2 = (Point *)b;
18.     if (sp1->x > sp2->x) return 1;
19.     else if (sp1->x < sp2->x) return -1;
20.     else if (sp1->y > sp2->y) return 1;
21.     return -1;
22. }
23.
24. double closest(long a, long b) {
25.     double d1, d2, d, xp;
26.     long i, j, k;
27.
28.     if(a == b)
29.         return MAX + 1.0;
30.     else if(b - a == 1)
31.         return dist(p[b], p[a]);
32.     else {
33.         int mid = (a + b) >> 1;
34.
35.         d1 = closest(a, mid);
36.         d2 = closest(mid + 1, b);
37.
38.         d = min(d1, d2);
39.
40.         xp = p[mid].x;
41.
42.         j = mid;
43.         do {
44.             k = mid + 1;
45.             while(xp - p[k].x < d && k <= b) {
46.                 d1 = dist(p[k], p[j]);
47.                 d = min(d, d1);
48.                 k++;
49.             }
50.             j--;
51.         } while (xp - p[j].x < d && j >= a);
52.
53.     return d;
54.     }
55. }
56.
57. int main() {
58.     int t;
59.     double d;
60.     while (scanf("%d", &t), t != 0) {
61.         for (int i = 0; i < t; i++)
62.             scanf("%lf%lf", &p[i].x, &p[i].y);
63.
64.         qsort(p, t, sizeof(p[0]), compare);
65.
66.         d = closest(0, t - 1);
67.         (d > MAX) ? puts("INFINITY") : printf("%.4lf\n", d);
68.     }
69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?