結果

問題 No.724 円と円の間の円
ユーザー ChanyuhChanyuh
提出日時 2020-03-03 11:29:14
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 8,165 bytes
コンパイル時間 2,105 ms
コンパイル使用メモリ 116,680 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-21 23:30:07
合計ジャッジ時間 2,712 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
5,248 KB
testcase_01 AC 16 ms
5,376 KB
testcase_02 AC 9 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 17 ms
5,376 KB
testcase_05 AC 12 ms
5,376 KB
testcase_06 AC 10 ms
5,376 KB
testcase_07 AC 6 ms
5,376 KB
testcase_08 AC 14 ms
5,376 KB
testcase_09 AC 14 ms
5,376 KB
testcase_10 AC 17 ms
5,376 KB
testcase_11 AC 14 ms
5,376 KB
testcase_12 AC 14 ms
5,376 KB
testcase_13 AC 14 ms
5,376 KB
testcase_14 AC 17 ms
5,376 KB
testcase_15 AC 5 ms
5,376 KB
testcase_16 AC 11 ms
5,376 KB
testcase_17 AC 16 ms
5,376 KB
testcase_18 AC 9 ms
5,376 KB
testcase_19 AC 8 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 20 ms
5,376 KB
testcase_23 AC 15 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

ld torad(int deg) {return (ld)(deg) * pi / 180;}
ld todeg(ld ang) {return ang * 180 / pi;}

struct Point {
    ld x, y;
    Point(ld x = 0.0, ld y = 0.0) : x(x), y(y) {}
    friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';}
};

Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
Point operator * (const Point &p, ld a) {return Point(p.x * a, p.y * a);}
Point operator * (ld a, const Point &p) {return Point(a * p.x, a * p.y);}
Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);}
Point operator / (const Point &p, ld a) {return Point(p.x / a, p.y / a);}
Point conj(const Point &p) {return Point(p.x, -p.y);}
Point rot(const Point &p, ld ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
Point rot90(const Point &p) {return Point(-p.y, p.x);}
ld cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
ld dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
ld norm(const Point &p) {return dot(p, p);}
ld abs(const Point &p) {return sqrt(dot(p, p));}
ld amp(const Point &p) {ld res = atan2(p.y, p.x); if (res < 0) res += pi*2; return res;}
bool eq(const Point &p, const Point &q) {return abs(p - q) < eps;}
bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > eps ? p.x < q.x : p.y < q.y);}
bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > eps ? p.x > q.x : p.y > q.y);}
Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}

int ccw(const Point &a, const Point &b, const Point &c) {
    if (cross(b-a, c-a) > eps) return 1;
    if (cross(b-a, c-a) < -eps) return -1;
    if (dot(b-a, c-a) < 0) return 2;
    if (norm(b-a) < norm(c-a)) return -2;
    return 0;
}

struct Line : vector<Point> {
    Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) {
        this->push_back(a);
        this->push_back(b);
    }
};


Point proj(Point p, Line l) {//射影
    ld t = dot(p - l[0], l[1] - l[0]) / norm(l[1] - l[0]);
    return l[0] + (l[1] - l[0]) * t;
}
Point refl(Point p, Line l) {//対象な点
    return p + (proj(p, l) - p) * 2;
}
bool isinterPL(Point p, Line l) {//点pが直線lに含まれるか
    return (abs(p - proj(p, l)) < eps);
}
bool isinterPS(Point p, Line s) {//点pが線分sに含まれるか
    return (ccw(s[0], s[1], p) == 0);
}
bool isinterLL(Line l, Line m) {//直線l,mが交わるか
    return (abs(cross(l[1] - l[0], m[1] - m[0])) > eps ||
            abs(cross(l[1] - l[0], m[0] - l[0])) < eps);
}
bool isinterSS(Line s, Line t) {//線分s,tが交わるか
    return (ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 && 
            ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0);
}
ld distancePL(Point p, Line l) {//点pと直線lの距離
    return abs(p - proj(p, l));
}
ld distancePS(Point p, Line s) {//点pと線分sの距離
    Point h = proj(p, s);
    if (isinterPS(h, s)) { return abs(p - h); }
    return min(abs(p - s[0]), abs(p - s[1]));
}
ld distanceLL(Line l, Line m) {//直線l,mの距離
    if (isinterLL(l, m)) return 0;
    else return distancePL(m[0], l);
}
ld distanceSS(Line s, Line t) {//線分s,tの距離
    if (isinterSS(s, t)) return 0;
    else return min(min(distancePS(s[0], t), distancePS(s[1], t)), min(distancePS(t[0], s), distancePS(t[1], s)));
}
struct Circle : Point{
    ld r;
    Circle(Point p = Point(0.0, 0.0), ld r = 0.0) : Point(p), r(r) {}
};


vector<Point> crosspoint(Line l, Line m) {
    vector<Point> res;
    ld d = cross(m[1] - m[0], l[1] - l[0]);
    if (abs(d) < eps) return vector<Point>();
    res.push_back(l[0] + (l[1] - l[0]) * cross(m[1] - m[0], m[1] - l[0]) / d);
    return res;
}
vector<Point> crosspoint(Circle e, Circle f) {
    vector<Point> res;
    ld d = abs(e - f);
    if (d < eps) return vector<Point>();
    ld rcos = (d * d + e.r * e.r - f.r * f.r) / (2.0 * d);
    if(e.r * e.r - rcos * rcos<0) return vector<Point>();
    ld rsin = sqrt(e.r * e.r - rcos * rcos);
    Point dir = (f - e) / d;
    Point p1 = e + dir * Point(rcos, rsin);
    Point p2 = e + dir * Point(rcos, -rsin);
    res.push_back(p1);
    if (!eq(p1, p2)) res.push_back(p2);
    return res;
}
vector<Point> crosspoint(Circle e, Line l) {
    vector<Point> res;
    Point p = proj(e, l);
    ld rcos = abs(e - p), rsin;
    if (rcos > e.r + eps) return vector<Point>();
    else if (e.r - rcos < eps) rsin = 0;
    if(e.r * e.r - rcos * rcos<0) return vector<Point>();
    else rsin = sqrt(e.r * e.r - rcos * rcos);
    Point dir = (l[1] - l[0]) / abs(l[1] - l[0]);
    Point p1 = p + dir * rsin;
    Point p2 = p - dir * rsin;
    res.push_back(p1);
    if (!eq(p1, p2)) res.push_back(p2);
    return res;
}


int n;
ld a,b;

void solve(){
  cin >> n >> a >> b;
  if(n%2==1){
    vector<Circle> cs={Circle(Point(a+b,0),b-a)};
    rep(i,(n-1)/2){
      //cout << cs[i].r << endl;
      ld left=amp(cs[i]-Point(a,0)),right=pi;
      rep(k,100){
        ld mid=(left+right)/2;
        ld d=(b*b-a*a-(b-a)*(b-a)+2*a*(b-a)*cos(mid))/(2*(a+b)-2*(b-a)*(cos(mid)));
        Circle c=Circle(Point(a+(a+d)*cos(mid),(a+d)*sin(mid)),d);
        for(Point p:crosspoint(c,cs[i])){
            //cout << p << endl;
        }
        if(crosspoint(c,cs[i]).empty()) right=mid;
        else left=mid;
        //cout << todeg(left) << " " << todeg(right) << endl;
      }
      ld d=(b*b-a*a-(b-a)*(b-a)+2*a*(b-a)*cos(left))/(2*(a+b)-2*(b-a)*(cos(left)));
      Circle c=Circle(Point(a+(a+d)*cos(left),(a+d)*sin(left)),d);
      //cout << c.r << endl;
      cs.push_back(c);
    }
    cout << cs[(n-1)/2].r << endl; 
  }
  else{
    vector<Circle> cs={};
    ld left=0,right=pi;
    rep(k,100){
        ld mid=(left+right)/2;
        ld d=(b*b-a*a-(b-a)*(b-a)+2*a*(b-a)*cos(mid))/(2*(a+b)-2*(b-a)*(cos(mid)));
        Circle c=Circle(Point(a+(a+d)*cos(mid),(a+d)*sin(mid)),d);
        if(c.y-c.r>0) right=mid;
        else left=mid;
        //cout << todeg(left) << " " << todeg(right) << endl;
    }
    ld d=(b*b-a*a-(b-a)*(b-a)+2*a*(b-a)*cos(left))/(2*(a+b)-2*(b-a)*(cos(left)));
    Circle c=Circle(Point(a+(a+d)*cos(left),(a+d)*sin(left)),d);
    //cout << c << " " << c.r << endl;
    cs.push_back(c);
    rep(i,(n-1)/2){
      ld left=amp(cs[i]-Point(a,0)),right=pi;
      rep(k,100){
        ld mid=(left+right)/2;
        ld d=(b*b-a*a-(b-a)*(b-a)+2*a*(b-a)*cos(mid))/(2*(a+b)-2*(b-a)*(cos(mid)));
        Circle c=Circle(Point(a+(a+d)*cos(mid),(a+d)*sin(mid)),d);
        for(Point p:crosspoint(c,cs[i])){
            //cout << p << endl;
        }
        if(crosspoint(c,cs[i]).empty()) right=mid;
        else left=mid;
        //cout << todeg(left) << " " << todeg(right) << endl;
      }
      ld d=(b*b-a*a-(b-a)*(b-a)+2*a*(b-a)*cos(left))/(2*(a+b)-2*(b-a)*(cos(left)));
      Circle c=Circle(Point(a+(a+d)*cos(left),(a+d)*sin(left)),d);
      //cout << c << " " << c.r << endl;
      cs.push_back(c);
    }
    cout << cs[(n-1)/2].r << endl; 
  }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}
0