結果

問題 No.724 円と円の間の円
ユーザー ChanyuhChanyuh
提出日時 2020-03-03 11:19:09
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 8,104 bytes
コンパイル時間 2,123 ms
コンパイル使用メモリ 116,188 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 21:55:53
合計ジャッジ時間 3,525 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 2 WA * 22
権限があれば一括ダウンロードができます

ソースコード

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) {//pl
return (abs(p - proj(p, l)) < eps);
}
bool isinterPS(Point p, Line s) {//ps
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) {//pl
return abs(p - proj(p, l));
}
ld distancePS(Point p, Line s) {//ps
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){
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);
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;
}
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=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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0