Submission #1000918

---

Source Code Expand

#include <bits/stdc++.h>

#ifdef AZN

#include "Azn.cpp"

#else
#define pln(...)
#define dbgln(...)
#endif

using namespace std;

typedef long double T; //scalar type, change to long long or __int128 if needed
typedef complex<T> Pt; // can be point (x, y) or vector from (0,0) to (x,y)
typedef pair<Pt, Pt> Line; // can be line or line segment
typedef pair<T, Pt> Circle; //(radius, center)
typedef vector<Pt> Poly; //points should be in CW or CCW order and unique
const T EPS = (T) (1e-9); //will be zero for integral T,  change as needed

/**
 * only need this if T is __int128
 */
/*T abs(T x) {
  return x < 0 ? -x : x;
}*/

/**
 * Determines whether a is equal b, works for floating point and integral types
 */
bool eq(T a, T b) {
  return abs(a - b) <= EPS;
}

T dot(Pt a, Pt b) {
  return real(conj(a) * b);
}

T cross(Pt a, Pt b) {
  return imag(conj(a) * b);
}

bool collinear(Pt a, Pt b) {
  return eq(cross(a, b), 0);
}

T point_line_dist(Pt p, Line l) {
  return abs(cross(p - l.first, l.second - l.first)) / abs(l.second - l.first);
}

typedef long long ll;
typedef double dd;

Pt read() {
  int x, y;
  cin >> x >> y;
  return Pt(x, y);
}

T angle(Pt u, Pt v) {
  return acos(dot(u, v) / abs(u) / abs(v)) / 2;
}

Circle calc_circ(T r, T ang, Pt orig, Pt u, Pt v) {
  if (cross(u, v) < 0) {
    return calc_circ(r, ang, orig, v, u);
  }
  u /= abs(u);
  u = polar((T) 1.0, arg(u) + ang);
  return {r, orig + u * (r / sin(ang))};
}

Line AB, AC, BC;
Pt A, B, C;

bool in_tri(Pt p) {
  return eq(abs(cross(B - A, C - A)), abs(cross(A - p, B - p)) + abs(cross(A - p, C - p)) + abs(cross(B - p, C - p)));
}

bool inter_side(Circle c) {
  return point_line_dist(c.second, AB) < c.first && point_line_dist(c.second, AC) < c.first &&
         point_line_dist(c.second, BC) < c.first;
}

bool check(Circle c1, Circle c2) {
  if (abs(c1.second - c2.second) < c1.first + c2.first) {
    return false; // circles intersect?
  }
  // circle not in triangle?
  if (!in_tri(c1.second) || !in_tri(c2.second))
    return false;
  // intersects a side?
  if (inter_side(c1) || inter_side(c2)) {
    return false;
  }
  return true;
}

void solve(ll test_num) {
  (void) test_num;
  A = read(), B = read(), C = read();
  AB = {A, B}, AC = {A, C}, BC = {B, C};
  T angA = angle(B - A, C - A), angB = angle(A - B, C - B), angC = angle(A - C, B - C);
  pln("angles:", angA, angB, angC);
  T low = 0.1, hig = 500;
  for (int its = 0; its < 100; ++its) {
    T mid = (low + hig) / 2.0;
    //mid = 0.8890555141;
    Circle cA = calc_circ(mid, angA, A, B - A, C - A);
    Circle cB = calc_circ(mid, angB, B, A - B, C - B);
    Circle cC = calc_circ(mid, angC, C, A - C, B - C);
    //pln(cA, cB, cC);
    if (check(cA, cB) || check(cA, cC) || check(cB, cC)) {
      low = mid;
    } else {
      hig = mid;
    }
  }
  cout << fixed << setprecision(10) << low << endl;
}


void init() {

}

int main() {
#ifdef AZN
  const auto start_time = chrono::system_clock::now();
  freopen("/home/azneye/Documents/Stuff/input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  init();
  ll tests = 1;
  //cin >> tests;
  for (ll test = 1; test <= tests; ++test) {
    solve(test);
  }
#ifdef AZN
  cerr << "Took: " << ((chrono::system_clock::now() - start_time).count() / 1e9) << " s" << endl;
#endif
  return 0;
}

Submission Info

Judge Result