Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<iostream>
- #include<vector>
- #include<cmath>
- #include<algorithm>
- #include<memory.h>
- #include<map>
- #include<set>
- #include<queue>
- #include<list>
- #include<sstream>
- #include<cstring>
- #include<numeric>
- using namespace std;
- double sqr(double a)
- {
- return a * a;
- }
- bool doubleEqual(double a, double b)
- {
- return fabs(a - b) < 1e-9;
- }
- bool doubleLessOrEqual(double a, double b)
- {
- return a < b || doubleEqual(a, b);
- }
- bool doubleLess(double a, double b)
- {
- return a < b && !doubleEqual(a, b);
- }
- bool doubleGreaterOrEqual(double a, double b)
- {
- return a > b || doubleEqual(a, b);
- }
- bool doubleGreater(double a, double b)
- {
- return a > b && !doubleEqual(a, b);
- }
- double mySqrt(double a)
- {
- if (doubleLess(a, 0))
- {
- throw "sqrt(-1)";
- }
- if (a < 0) return 0;
- return sqrt(a);
- }
- struct Point {
- private: double x, y;
- public:
- Point() : x(0), y(0) {}
- Point(double x, double y) : x(x), y(y) {}
- void scan()
- {
- scanf("%lf %lf", &x, &y);
- }
- void print() const
- {
- printf("%.10lf %.10lf\n", x, y);
- }
- Point operator+(const Point & p) const
- {
- return Point(x + p.x, y + p.y);
- }
- Point operator-(const Point & p) const
- {
- return Point(x - p.x, y - p.y);
- }
- Point operator-() const
- {
- return Point(-x, -y);
- }
- Point operator*(double k) const
- {
- return Point(x * k, y * k);
- }
- Point operator/(double k) const
- {
- return Point(x / k, y / k);
- }
- double operator%(const Point & p) const
- {
- return x * p.x + y * p.y;
- }
- double operator*(const Point & p) const
- {
- return x * p.y - y * p.x;
- }
- double length() const
- {
- return mySqrt(*this % *this);
- }
- double distTo(const Point & p) const
- {
- return (*this - p).length();
- }
- double distTo(const Point & A, const Point & B) const
- {
- double d = A.distTo(B);
- if (doubleEqual(d, 0))
- {
- throw "A = B";
- }
- double s = (*this - A) * (*this - B);
- return fabs(s) / d;
- }
- Point normalize(double k = 1) const
- {
- double len = length();
- if (doubleEqual(len, 0))
- {
- if (doubleEqual(k, 0))
- {
- return Point();
- }
- throw "zero-size vector";
- }
- return *this * (k / len);
- }
- Point getH(const Point & A, const Point & B) const
- {
- Point C = *this;
- Point v = B - A;
- Point u = C - A;
- double k = v % u / v.length();
- v = v.normalize(k);
- Point H = A + v;
- return H;
- }
- Point rotate() const
- {
- return Point(-y, x);
- }
- Point rotate(double alpha) const
- {
- return rotate(cos(alpha), sin(alpha));
- }
- Point rotate(double cosa, double sina) const
- {
- Point v = *this;
- Point u = v.rotate();
- Point w = v * cosa + u * sina;
- return w;
- }
- bool isZero() const
- {
- return doubleEqual(x, 0) && doubleEqual(y, 0);
- }
- bool isOnLine(const Point & A, const Point & B) const
- {
- return doubleEqual((A - *this) * (B - *this), 0);
- }
- bool isInSegment(const Point & A, const Point & B) const
- {
- return isOnLine(A, B) && doubleLessOrEqual((A - *this) % (B - *this), 0);
- }
- bool isInSegmentStrictly(const Point & A, const Point & B) const
- {
- return isOnLine(A, B) && doubleLess((A - *this) % (B - *this), 0);
- }
- double getAngle() const
- {
- return atan2(y, x);
- }
- double getAngle(Point u) const
- {
- Point v = *this;
- return atan2(v * u, v % u);
- }
- };
- const int N = 1e3;
- int n;
- pair<Point, double> a[N];
- vector<int> g[N];
- bool used[2][N];
- int color[2][N];
- void addEdge(int a, int b) {
- g[a].push_back(b);
- g[b].push_back(a);
- }
- void dfs(int v, int cur, int t) {
- used[t][v] = true;
- color[t][v] = cur;
- for (auto c : g[v]) {
- if (!used[t][c]) {
- dfs(c, cur ^ 1, t);
- }
- }
- }
- bool check(double d) {
- for (int i = 0; i < n; i++) {
- g[i].clear();
- used[0][i] = used[1][i] = false;
- color[0][i] = color[1][i] = -1;
- }
- set<int> q;
- for (int i = 0; i < n; i++) {
- for (int j = i + 1; j < n; j++) {
- if (i == j)
- continue;
- if (a[i].first.distTo(a[j].first) <= a[i].second + a[j].second + d) {
- return false;
- }
- else {
- if (a[i].first.distTo(a[j].first) <= a[i].second + a[j].second + d + d) {
- addEdge(i, j);
- q.insert(i);
- q.insert(j);
- }
- }
- }
- }
- for (auto c : q) {
- if (!used[0][c]) {
- dfs(c, 0, 0);
- }
- if (!used[1][c]) {
- dfs(c, 1, 1);
- }
- }
- int fails = 0;
- for (int t = 0; t < 2; t++) {
- bool fail = false;
- for (int i = 0; i < n; i++) {
- for (auto v : g[i]) {
- if (color[t][i] == color[t][v]) {
- fail = true;
- }
- }
- }
- if (fail)
- fails++;
- }
- return fails != 2;
- }
- int main() {
- //freopen("input.txt", "r", stdin);
- scanf("%d", &n);
- for (int i = 0; i < n; i++){
- a[i].first.scan();
- scanf("%lf", &a[i].second);
- }
- double l = 0;
- double r = 1e12;
- while (!doubleEqual(r, l)) {
- double mid = (r + l) / 2.0;
- if (check(mid)) {
- l = mid;
- }
- else {
- r = mid;
- }
- }
- printf("%lf", l);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement