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; }