CodeFestival 2016 GrandFinal

B - Inscribed Bicycle (500)

B - Inscribed Bicycle

概要

３頂点からなる三角形について、
三角形の内部に半径が同じ２つの円を重ならないように配置するとき、
配置できる円の半径の最大値を求めよ。

制約

方針

半径が最大となるとき、２円は接している。
このとき、2円のどちらもが接している辺の長さは、半径とその両端の２角を用いて
と表せる。
ここからを求める。

解答

Submission #3917568 - CODE FESTIVAL 2016 Grand Final(Parallel)

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
struct pdd{double x, y;};
 
typedef long long ll;
typedef unsigned long long ull;
 
double dist(pdd a, pdd b){
	double sqd = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
	return sqrt(sqd);
}
 
double calccos(double a, double b, double c){
	return (b*b + c*c - a*a) / (2*b*c);
}
 
double calcr(double l, double th1, double th2){
	return l / (2 + 1 / tan(th1 / 2) + 1 / tan(th2 / 2));
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	pdd p1, p2, p3;
	cin >> p1.x >> p1.y;
	cin >> p2.x >> p2.y;
	cin >> p3.x >> p3.y;
 
	double l1, l2, l3;
	l1 = dist(p2, p3);
	l2 = dist(p1, p3);
	l3 = dist(p1, p2);
 
	double th1, th2, th3;
	th1 = acos(calccos(l1, l2, l3));
	th2 = acos(calccos(l2, l1, l3));
	th3 = acos(calccos(l3, l1, l2));
 
	double r1, r2, r3;
	r1 = calcr(l1, th2, th3);
	r2 = calcr(l2, th1, th3);
	r3 = calcr(l3, th1, th2);
 
	cout << fixed << setprecision(12) << max({r1, r2, r3}) << endl;
}