Submission #4233444

---

Source Code Expand

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

typedef long long ll;
 
using tpl = tuple<int, int, int>;
typedef pair<int,int> pii;

void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}

#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) (EQ((a).real(),(b).real()) && EQ((a).imag(),(b).imag()))

typedef complex<double> P;
typedef pair<P,P> Edge;
typedef long long ll;

const double PI=4*atan(1.0);

// 内積
double dot(const P &a, const P &b) {
  return (a.real() * b.real() + a.imag() * b.imag());
}
// 外積
double cross(const P &a, const P &b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}

// 点a,bを通る直線と点cの間の距離
double distance_l_p(const P &a, const P &b, const P &c) {
  return abs(cross(b-a, c-a)) / abs(b-a);
}

// 2ベクトル間の角度
// aからbへ左周りで何度か(0->2*PI)
double diffAngle(const P &a,const P &b){
  double angle=atan2(cross(a,b),dot(a,b));
  if(angle<0)
    return 2*PI+angle;
  return angle;
}

// 座標の回転(座標pにある点を,半時計回りにa(ラジアン)回転)
P roundPoint(const P &p,double a){
  return P(cos(a)*p.real()-sin(a)*p.imag(),sin(a)*p.real()+cos(a)*p.imag());
}


int X[3];
int Y[3];

double dist(int x1, int y1, int x2, int y2){
    return sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
}

P calc_center(P p1, P p2, P p3, double mid){
    P basev = p2 - p1; basev /= abs(basev);
    // cout << basev << endl;
    double ang = diffAngle(p2 - p1, p3 - p1);
    if(ang >= PI){
        double ang2 = (2 * PI - ang);
        // basevを左回りにang/2 回転する
        P basev2 = roundPoint(basev, ang2 / 2 + ang);
        // 長さを特定する
        double len = mid / sin(ang2 / 2);
        P c1 = basev2 * len + p1;
        return c1;
    }
    else{
        // basevを左回りにang/2 回転する
        P basev2 = roundPoint(basev, ang/2);
        // 長さを特定する
        double len = mid / sin(ang / 2);
        P c1 = basev2 * len + p1;
        return c1;
    }
}

int main(){

    

    for(int i = 0; i < 3; i++) cin >> X[i] >> Y[i];
    double ans = 0;
    for(int i = 0; i < 3; i++){
        int x1 = X[i];
        int y1 = Y[i];
        int x2 = X[(i+1)%3];
        int y2 = Y[(i+1)%3];
        int x3 = X[(i+2)%3];
        int y3 = Y[(i+2)%3];
        double d1 = dist(x2, y2, x3, y3);
        double d2 = dist(x1, y1, x3, y3);
        double d3 = dist(x1, y1, x2, y2);
        double cx = d1 / (d1 + d2 + d3) * x1 + d2 / (d1 + d2 + d3) * x2 + d3 / (d1 + d2 + d3) * x3;
        double cy = d1 / (d1 + d2 + d3) * y1 + d2 / (d1 + d2 + d3) * y2 + d3 / (d1 + d2 + d3) * y3;
        // cout << cx << ", " << cy << endl;
        double rmax = distance_l_p(P(x1, y1), P(x2, y2), P(cx, cy));
        double ub = rmax;
        double lb = 0;
        for(int ite = 0; ite < 200; ite++){
            double mid = (ub + lb) / 2;
            // midを半径とした円を、p1とp2に対しておく
            // もし交差するのならX
            // しないのならOK
            // で判定してく
            P c1 = calc_center(P(x1, y1), P(x2, y2), P(x3, y3), mid);
            P c2 = calc_center(P(x2, y2), P(x1, y1), P(x3, y3), mid);
            // cout << c1 << ", " << c2 << ", " << mid << endl;
            if(abs(c1-c2) >= mid * 2){
                lb = mid;
            }
            else{
                ub = mid;
            }
        }
        ans = max(ans, ub);
    }
    printf("%.10f\n", ans);

    return 0;
}

Submission Info

Judge Result