CODE FESTIVAL 2016 Grand Final(Parallel) B - Inscribed Bicycle

• 問題

問題概要

A(x1,y1), B(x2,y2), C(x3,y3)が与えられる.
ABC内部に半径の同じ円を2つ描く時,最大の半径を求めよ.

解法

BC,CA,ABをそれぞれa,b,cとする.
またcが最大の辺とする.
内接円の中心O,半径r, 内部に描く二つの円の半径をxとすると,以下のようになる.

(図が汚いが各円と辺は接している.)
ODEとOABは相似なため,DE = c * (r-x) / x,
DE = 2x なので c(r-x)/x = 2xを解けば良い.

メモ

中学受験っぽい.内心に注目するのが出てこなかった.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;

int main(){
  double x1,y1,x2,y2,x3,y3;
  cin >> x1 >> y1;
  cin >> x2 >> y2;
  cin >> x3 >> y3;
  double a,b,c,r,d,x;
  a = hypot(x1-x2,y1-y2);
  b = hypot(x2-x3,y2-y3);
  c = hypot(x3-x1,y3-y1);
  r = abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))/(a+b+c);
  d = max(a,max(b,c));
  x = d/(2+d/r);
  printf("%.12lf",x);
  return 0;
}