Gym - 100625G Getting Through 计算几何+并查集

http://codeforces.com/gym/100625/attachments/download/3213/2013-benelux-algorithm-programming-contest-bapc-13-en.pdf

题意：平面内给你一个y轴为左边界，宽度为w的长条形区域，区域内n个半径为r的圆，问你最大能够通过这个区域的圆的半径是多少。

思路：这题和POJ 3798差不是很多，感觉像是简化版。之前鲍佳提到过那个题，谈到过并查集，不过我没写过。知道并查集这题就很好想了，在圆与圆，圆与左右边界之间都连一条边，边长就是他们的距离。那么答案就是这些边中的一条了。现在将边排好序，从小到大加到并查集里面，每加一次find一下左边界和右边界是不是连到一起了，如果连起来了，那这条边就是答案，直接输出。最后还没连起来的话，就无解了。

 #pragma comment(linker, "/STACK:1000000000")

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <algorithm>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <string>

 #include <cstring>

 #include <map>

 #include <stack>

 #include <set>

 #define LL long long

 #define MAXN 1005

 #define INF 0x3f3f3f3f

 #define eps 1e-8

 using namespace std;

 struct Circle

 {

     int x, y, r;

 };

 struct Node

 {

     int from, to;

     double dis;

     Node(int from, int to, double dis):from(from), to(to), dis(dis){};

 };

 Circle a[MAXN];

 vector<Node> p;

 int father[MAXN];

 double GetDis(int u, int v)

 {

     double x = abs(a[u].x - a[v].x);

     double y = abs(a[u].y - a[v].y);

     double r = a[u].r + a[v].r;

     return sqrt(x * x + y * y) - r;

 }

 int find(int x)

 {

     if(x == father[x]) return x;

     father[x] = find(father[x]);

     return father[x];

 }

 bool compare(Node a, Node b)

 {

     return a.dis < b.dis;

 }

 int main()

 {

 #ifndef ONLINE_JUDGE

     freopen("in.txt", "r", stdin);

     //freopen("out.txt", "w", stdout);

 #endif // OPEN_FILE

     int T;

     scanf("%d", &T);

     while(T--){

         int w;

         scanf("%d", &w);

         int n;

         scanf("%d", &n);

         if(n == ){

             double ans = w;

             ans /= ;

             printf("%.7lf\n", ans);

             continue;

         }

         for(int i = ; i <= n; i++){

             scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);

         }

         for(int i = ; i <= n + ; i++){

             father[i] = i;

         }

         p.clear();

         for(int i = ; i <= n; i++){

             for(int j = i + ; j <= n; j++){

                 p.push_back(Node(i, j, GetDis(i, j)));

             }

         }

         for(int i = ; i <= n; i++){

             p.push_back(Node(i, , a[i].x - a[i].r));

             p.push_back(Node(i, n + , w - a[i].x - a[i].r));

         }

         n++;

         sort(p.begin(), p.end(), compare);

         int m = p.size();

         double ans = ;

         bool flag = false;

         for(int i = ; i < p.size(); i++){

             int x = find(p[i].from);

             int y = find(p[i].to);

             if(x == y) continue;

             father[x] = y;

             x = find();

             y = find(n);

             if(x == y && p[i].dis > ){

                 ans = p[i].dis;

                 flag = true;

                 break;

             }

         }

         if(flag){

             printf("%.7lf\n", ans / );

         }

         else{

             printf("0\n");

         }

     }

 }

巴特西

Gym - 100625G Getting Through 计算几何+并查集

最新文章

热门文章