Advertisement
Hippskill

Untitled

Jan 17th, 2016
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.94 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<vector>
  4. #include<cmath>
  5. #include<algorithm>
  6. #include<memory.h>
  7. #include<map>
  8. #include<set>
  9. #include<queue>
  10. #include<list>
  11. #include<sstream>
  12. #include<cstring>
  13. #include<numeric>
  14. using namespace std;
  15.  
  16.  
  17. double sqr(double a)
  18. {
  19.     return a * a;
  20. }
  21.  
  22.  
  23. bool doubleEqual(double a, double b)
  24. {
  25.     return fabs(a - b) < 1e-9;
  26. }
  27.  
  28.  
  29. bool doubleLessOrEqual(double a, double b)
  30. {
  31.     return a < b || doubleEqual(a, b);
  32. }
  33.  
  34.  
  35. bool doubleLess(double a, double b)
  36. {
  37.     return a < b && !doubleEqual(a, b);
  38. }
  39.  
  40.  
  41. bool doubleGreaterOrEqual(double a, double b)
  42. {
  43.     return a > b || doubleEqual(a, b);
  44. }
  45.  
  46.  
  47. bool doubleGreater(double a, double b)
  48. {
  49.     return a > b && !doubleEqual(a, b);
  50. }
  51.  
  52.  
  53. double mySqrt(double a)
  54. {
  55.     if (doubleLess(a, 0))
  56.     {
  57.         throw "sqrt(-1)";
  58.     }
  59.     if (a < 0) return 0;
  60.     return sqrt(a);
  61. }
  62.  
  63.  
  64. struct Point {
  65. private: double x, y;
  66. public:
  67.     Point() : x(0), y(0) {}
  68.  
  69.     Point(double x, double y) : x(x), y(y) {}
  70.  
  71.         void scan()
  72.     {
  73.         scanf("%lf %lf", &x, &y);
  74.     }
  75.  
  76.     void print() const
  77.     {
  78.         printf("%.10lf %.10lf\n", x, y);
  79.     }
  80.  
  81.     Point operator+(const Point & p) const
  82.     {
  83.         return Point(x + p.x, y + p.y);
  84.     }
  85.  
  86.     Point operator-(const Point & p) const
  87.     {
  88.         return Point(x - p.x, y - p.y);
  89.     }
  90.  
  91.     Point operator-() const
  92.     {
  93.         return Point(-x, -y);
  94.     }
  95.  
  96.     Point operator*(double k) const
  97.     {
  98.         return Point(x * k, y * k);
  99.     }
  100.  
  101.     Point operator/(double k) const
  102.     {
  103.         return Point(x / k, y / k);
  104.     }
  105.  
  106.     double operator%(const Point & p) const
  107.     {
  108.         return x * p.x + y * p.y;
  109.     }
  110.  
  111.     double operator*(const Point & p) const
  112.     {
  113.         return x * p.y - y * p.x;
  114.     }
  115.  
  116.     double length() const
  117.     {
  118.         return mySqrt(*this % *this);
  119.     }
  120.  
  121.     double distTo(const Point & p) const
  122.     {
  123.         return (*this - p).length();
  124.     }
  125.  
  126.     double distTo(const Point & A, const Point & B) const
  127.     {
  128.         double d = A.distTo(B);
  129.         if (doubleEqual(d, 0))
  130.         {
  131.             throw "A = B";
  132.         }
  133.         double s = (*this - A) * (*this - B);
  134.         return fabs(s) / d;
  135.     }
  136.  
  137.     Point normalize(double k = 1) const
  138.     {
  139.         double len = length();
  140.         if (doubleEqual(len, 0))
  141.         {
  142.             if (doubleEqual(k, 0))
  143.             {
  144.                 return Point();
  145.             }
  146.             throw "zero-size vector";
  147.         }
  148.         return *this * (k / len);
  149.     }
  150.  
  151.     Point getH(const Point & A, const Point & B) const
  152.     {
  153.         Point C = *this;
  154.         Point v = B - A;
  155.         Point u = C - A;
  156.         double k = v % u / v.length();
  157.         v = v.normalize(k);
  158.         Point H = A + v;
  159.         return H;
  160.     }
  161.  
  162.     Point rotate() const
  163.     {
  164.         return Point(-y, x);
  165.     }
  166.  
  167.     Point rotate(double alpha) const
  168.     {
  169.         return rotate(cos(alpha), sin(alpha));
  170.     }
  171.  
  172.     Point rotate(double cosa, double sina) const
  173.     {
  174.         Point v = *this;
  175.         Point u = v.rotate();
  176.         Point w = v * cosa + u * sina;
  177.         return w;
  178.     }
  179.  
  180.     bool isZero() const
  181.     {
  182.         return doubleEqual(x, 0) && doubleEqual(y, 0);
  183.     }
  184.  
  185.     bool isOnLine(const Point & A, const Point & B) const
  186.     {
  187.         return doubleEqual((A - *this) * (B - *this), 0);
  188.     }
  189.  
  190.     bool isInSegment(const Point & A, const Point & B) const
  191.     {
  192.         return isOnLine(A, B) && doubleLessOrEqual((A - *this) % (B - *this), 0);
  193.     }
  194.  
  195.     bool isInSegmentStrictly(const Point & A, const Point & B) const
  196.     {
  197.         return isOnLine(A, B) && doubleLess((A - *this) % (B - *this), 0);
  198.     }
  199.  
  200.     double getAngle() const
  201.     {
  202.         return atan2(y, x);
  203.     }
  204.  
  205.     double getAngle(Point u) const
  206.     {
  207.         Point v = *this;
  208.         return atan2(v * u, v % u);
  209.     }
  210.  
  211. };
  212.  
  213. const int N = 1e3;
  214.  
  215.  
  216. int n;
  217.  
  218. pair<Point, double> a[N];
  219.  
  220. vector<int> g[N];
  221.  
  222. bool used[2][N];
  223. int color[2][N];
  224.  
  225. void addEdge(int a, int b) {
  226.     g[a].push_back(b);
  227.     g[b].push_back(a);
  228. }
  229.  
  230. void dfs(int v, int cur, int t) {
  231.     used[t][v] = true;
  232.     color[t][v] = cur;
  233.     for (auto c : g[v]) {
  234.         if (!used[t][c]) {
  235.             dfs(c, cur ^ 1, t);
  236.         }
  237.     }
  238. }
  239.  
  240. bool check(double d) {
  241.     for (int i = 0; i < n; i++) {
  242.         g[i].clear();
  243.         used[0][i] = used[1][i] = false;
  244.         color[0][i] = color[1][i] = -1;
  245.     }
  246.  
  247.     set<int> q;
  248.     for (int i = 0; i < n; i++) {
  249.         for (int j = i + 1; j < n; j++) {
  250.             if (i == j)
  251.                 continue;
  252.             if (a[i].first.distTo(a[j].first) <= a[i].second + a[j].second + d) {
  253.                 return false;
  254.             }
  255.             else {
  256.                 if (a[i].first.distTo(a[j].first) <= a[i].second + a[j].second + d + d) {
  257.                     addEdge(i, j);
  258.                     q.insert(i);
  259.                     q.insert(j);
  260.                 }
  261.             }
  262.         }
  263.     }
  264.  
  265.     for (auto c : q) {
  266.         if (!used[0][c]) {
  267.             dfs(c, 0, 0);
  268.         }
  269.         if (!used[1][c]) {
  270.  
  271.             dfs(c, 1, 1);
  272.         }
  273.     }
  274.  
  275.     int fails = 0;
  276.     for (int t = 0; t < 2; t++) {
  277.         bool fail = false;
  278.         for (int i = 0; i < n; i++) {
  279.             for (auto v : g[i]) {
  280.                 if (color[t][i] == color[t][v]) {
  281.                     fail = true;
  282.                 }
  283.             }
  284.         }
  285.         if (fail)
  286.             fails++;
  287.     }
  288.    
  289.     return fails != 2;
  290.  
  291. }
  292.  
  293. int main() {
  294.     //freopen("input.txt", "r", stdin);
  295.     scanf("%d", &n);
  296.     for (int i = 0; i < n; i++){
  297.         a[i].first.scan();
  298.         scanf("%lf", &a[i].second);
  299.     }
  300.  
  301.     double l = 0;
  302.     double r = 1e12;
  303.     while (!doubleEqual(r, l)) {
  304.         double mid = (r + l) / 2.0;
  305.         if (check(mid)) {
  306.             l = mid;
  307.         }
  308.         else {
  309.             r = mid;
  310.         }
  311.     }
  312.     printf("%lf", l);
  313.  
  314.     return 0;
  315. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement