Submission #2151076

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

using Complex = complex<double>;

bool isinter(Complex c1, double r1, Complex c2, double r2){
  double d = abs(c1-c2);
  return r1+r2 >= d;
}

double cross(Complex c1, Complex c2){
  return c1.real() * c2.imag() - c1.imag() * c2.real();
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  double lb = 0., ub = 1e5;
  vector<Complex> xs(3);
  vector<double> rs(3);
  REP(i,3){
	double x, y;
	cin >> x >> y;
	xs[i] = Complex(x, y);
  }
  REP(i,3) rs[i] = abs(xs[i] - xs[(i+1)%3]);
  double s = accumulate(ALL(rs), 0.) / 2.;
  double S = accumulate(ALL(rs), s, [s](double acc, double x){ return acc * (s-x); });
  S = sqrt(S);
  ub = S / s;

  vector<Complex> dir(3);
  vector<double> sn(3);
  REP(i,3){
	auto d1 = (xs[(i+1)%3] - xs[i]);
	auto d2 = (xs[(i+2)%3] - xs[i]);
	dir[i] = (d1 * abs(d2) + d2 * abs(d1)) / (abs(d1) + abs(d2));
	d1 /= abs(d1);
	dir[i] /= abs(dir[i]);
	sn[i] = abs(cross(d1, dir[i]));
  }

  REP(_,100){
	double r = (lb + ub) / 2.;
	vector<Complex> cs(3);
	REP(i,3) cs[i] = xs[i] + dir[i] * r / sn[i];

	bool ok = false;
	REP(i,3) REP(j,3){
	  if(i == j) continue;
	  if(!isinter(cs[i], r, cs[j], r)){
		ok = true;
		int sg = cross(cs[i] - xs[0], xs[0] - xs[1]) > 0? 1: -1;
		REP(ii,3){
		  int sg_ = cross(cs[i] - xs[ii], xs[ii] - xs[(ii+1)%3]) > 0? 1: -1;
		  ok &= sg == sg_;
		}

		sg = cross(cs[j] - xs[0], xs[0] - xs[1]) > 0? 1: -1;
		REP(ii,3){
		  int sg_ = cross(cs[j] - xs[ii], xs[ii] - xs[(ii+1)%3]) > 0? 1: -1;
		  ok &= sg == sg_;
		}

		if(ok) i = j = 3;
		break;
	  }
	}
	
	if(ok) lb = r;
	else ub = r;
  }
  cout << fixed << setprecision(12) << lb << endl;

  return 0;
}

Submission Info

Judge Result