結果
問題 | No.724 円と円の間の円 |
ユーザー |
![]() |
提出日時 | 2018-08-03 23:13:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,498 ms / 2,000 ms |
コード長 | 16,355 bytes |
コンパイル時間 | 3,196 ms |
コンパイル使用メモリ | 222,884 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-19 17:39:34 |
合計ジャッジ時間 | 22,658 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;struct Precision{Precision(){cout<<fixed<<setprecision(12);}}precision_beet;#define EPS (1e-10)#define equals(a,b) (fabs((a)-(b)) < EPS)#define PI 3.141592653589793238// COUNTER CLOCKWISEstatic const Int CCW_COUNTER_CLOCKWISE = 1;static const Int CCW_CLOCKWISE = -1;static const Int CCW_ONLINE_BACK = 2;static const Int CCW_ONLINE_FRONT = -2;static const Int CCW_ON_SEGMENT = 0;//Intercsect Circle & Circlestatic const Int ICC_SEPERATE = 4;static const Int ICC_CIRCUMSCRIBE = 3;static const Int ICC_INTERSECT = 2;static const Int ICC_INSCRIBE = 1;static const Int ICC_CONTAIN = 0;struct Point{double x,y;Point(){}Point(double x,double y) :x(x),y(y){}Point operator+(Point p) {return Point(x+p.x,y+p.y);}Point operator-(Point p) {return Point(x-p.x,y-p.y);}Point operator*(double k){return Point(x*k,y*k);}Point operator/(double k){return Point(x/k,y/k);}double norm(){return x*x+y*y;}double abs(){return sqrt(norm());}bool operator < (const Point &p) const{return x!=p.x?x<p.x:y<p.y;//grid-point only//return !equals(x,p.x)?x<p.x:!equals(y,p.y)?y<p.y:0;}bool operator == (const Point &p) const{return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;}};struct EndPoint{Point p;Int seg,st;EndPoint(){}EndPoint(Point p,Int seg,Int st):p(p),seg(seg),st(st){}bool operator<(const EndPoint &ep)const{if(p.y==ep.p.y) return st<ep.st;return p.y<ep.p.y;}};istream &operator >> (istream &is,Point &p){is>>p.x>>p.y;return is;}ostream &operator << (ostream &os,Point p){os<<fixed<<setprecision(12)<<p.x<<" "<<p.y;return os;}bool sort_x(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}bool sort_y(Point a,Point b){return a.y!=b.y?a.y<b.y:a.x<b.x;}typedef Point Vector;typedef vector<Point> Polygon;istream &operator >> (istream &is,Polygon &p){for(Int i=0;i<(Int)p.size();i++) cin>>p[i];return is;}struct Segment{Point p1,p2;Segment(){}Segment(Point p1, Point p2):p1(p1),p2(p2){}};typedef Segment Line;istream &operator >> (istream &is,Segment &s){is>>s.p1>>s.p2;return is;}struct Circle{Point c;double r;Circle(){}Circle(Point c,double r):c(c),r(r){}};istream &operator >> (istream &is,Circle &c){is>>c.c>>c.r;return is;}double norm(Vector a){return a.x*a.x+a.y*a.y;}double abs(Vector a){return sqrt(norm(a));}double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}double cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}Point orth(Point p){return Point(-p.y,p.x);}bool isOrthogonal(Vector a,Vector b){return equals(dot(a,b),0.0);}bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){return isOrthogonal(a1-a2,b1-b2);}bool isOrthogonal(Segment s1,Segment s2){return equals(dot(s1.p2-s1.p1,s2.p2-s2.p1),0.0);}bool isParallel(Vector a,Vector b){return equals(cross(a,b),0.0);}bool isParallel(Point a1,Point a2,Point b1,Point b2){return isParallel(a1-a2,b1-b2);}bool isParallel(Segment s1,Segment s2){return equals(cross(s1.p2-s1.p1,s2.p2-s2.p1),0.0);}Point project(Segment s,Point p){Vector base=s.p2-s.p1;double r=dot(p-s.p1,base)/norm(base);return s.p1+base*r;}Point reflect(Segment s,Point p){return p+(project(s,p)-p)*2.0;}double arg(Vector p){return atan2(p.y,p.x);}Vector polar(double a,double r){return Point(cos(r)*a,sin(r)*a);}Int ccw(Point p0,Point p1,Point p2);bool intersectSS(Point p1,Point p2,Point p3,Point p4);bool intersectSS(Segment s1,Segment s2);bool intersectPS(Polygon p,Segment l);Int intersectCC(Circle c1,Circle c2);bool intersectSC(Segment s,Circle c);double getDistanceLP(Line l,Point p);double getDistanceSP(Segment s,Point p);double getDistanceSS(Segment s1,Segment s2);Point getCrossPointSS(Segment s1,Segment s2);Point getCrossPointLL(Line l1,Line l2);Polygon getCrossPointCL(Circle c,Line l);Polygon getCrossPointCC(Circle c1,Circle c2);Int contains(Polygon g,Point p);Polygon andrewScan(Polygon s);Polygon convex_hull(Polygon ps);double diameter(Polygon s);bool isConvex(Polygon p);double area(Polygon s);Polygon convexCut(Polygon p,Line l);Line bisector(Point p1,Point p2);Vector translate(Vector v,double theta);vector<Line> corner(Line l1,Line l2);vector<vector<pair<Int, double> > >segmentArrangement(vector<Segment> &ss, Polygon &ps);Int ccw(Point p0,Point p1,Point p2){Vector a = p1-p0;Vector b = p2-p0;if(cross(a,b) > EPS) return CCW_COUNTER_CLOCKWISE;if(cross(a,b) < -EPS) return CCW_CLOCKWISE;if(dot(a,b) < -EPS) return CCW_ONLINE_BACK;if(a.norm()<b.norm()) return CCW_ONLINE_FRONT;return CCW_ON_SEGMENT;}bool intersectSS(Point p1,Point p2,Point p3,Point p4){return (ccw(p1,p2,p3)*ccw(p1,p2,p4) <= 0 &&ccw(p3,p4,p1)*ccw(p3,p4,p2) <= 0 );}bool intersectSS(Segment s1,Segment s2){return intersectSS(s1.p1,s1.p2,s2.p1,s2.p2);}bool intersectPS(Polygon p,Segment l){Int n=p.size();for(Int i=0;i<n;i++)if(intersectSS(Segment(p[i],p[(i+1)%n]),l)) return 1;return 0;}Int intersectCC(Circle c1,Circle c2){if(c1.r<c2.r) swap(c1,c2);double d=abs(c1.c-c2.c);double r=c1.r+c2.r;if(equals(d,r)) return ICC_CIRCUMSCRIBE;if(d>r) return ICC_SEPERATE;if(equals(d+c2.r,c1.r)) return ICC_INSCRIBE;if(d+c2.r<c1.r) return ICC_CONTAIN;return ICC_INTERSECT;}bool intersectSC(Segment s,Circle c){return getDistanceSP(s,c.c)<=c.r;}Int intersectCS(Circle c,Segment s){if(norm(project(s,c.c)-c.c)-c.r*c.r>EPS) return 0;double d1=abs(c.c-s.p1),d2=abs(c.c-s.p2);if(d1<c.r+EPS&&d2<c.r+EPS) return 0;if((d1<c.r-EPS&&d2>c.r+EPS)||(d1>c.r+EPS&&d2<c.r-EPS)) return 1;Point h=project(s,c.c);if(dot(s.p1-h,s.p2-h)<0) return 2;return 0;}double getDistanceLP(Line l,Point p){return abs(cross(l.p2-l.p1,p-l.p1)/abs(l.p2-l.p1));}double getDistanceSP(Segment s,Point p){if(dot(s.p2-s.p1,p-s.p1) < 0.0 ) return abs(p-s.p1);if(dot(s.p1-s.p2,p-s.p2) < 0.0 ) return abs(p-s.p2);return getDistanceLP(s,p);}double getDistanceSS(Segment s1,Segment s2){if(intersectSS(s1,s2)) return 0.0;return min(min(getDistanceSP(s1,s2.p1),getDistanceSP(s1,s2.p2)),min(getDistanceSP(s2,s1.p1),getDistanceSP(s2,s1.p2)));}Point getCrossPointSS(Segment s1,Segment s2){for(Int k=0;k<2;k++){if(getDistanceSP(s1,s2.p1)<EPS) return s2.p1;if(getDistanceSP(s1,s2.p2)<EPS) return s2.p2;swap(s1,s2);}Vector base=s2.p2-s2.p1;double d1=abs(cross(base,s1.p1-s2.p1));double d2=abs(cross(base,s1.p2-s2.p1));double t=d1/(d1+d2);return s1.p1+(s1.p2-s1.p1)*t;}Point getCrossPointLL(Line l1,Line l2){double a=cross(l1.p2-l1.p1,l2.p2-l2.p1);double b=cross(l1.p2-l1.p1,l1.p2-l2.p1);if(abs(a)<EPS&&abs(b)<EPS) return l2.p1;return l2.p1+(l2.p2-l2.p1)*(b/a);}Polygon getCrossPointCL(Circle c,Line l){Polygon ps;Point pr=project(l,c.c);Vector e=(l.p2-l.p1)/abs(l.p2-l.p1);if(equals(getDistanceLP(l,c.c),c.r)){ps.emplace_back(pr);return ps;}double base=sqrt(c.r*c.r-norm(pr-c.c));ps.emplace_back(pr+e*base);ps.emplace_back(pr-e*base);return ps;}Polygon getCrossPointCS(Circle c,Segment s){Line l(s);Polygon res=getCrossPointCL(c,l);if(intersectCS(c,s)==2) return res;if(res.size()>1u){if(dot(l.p1-res[0],l.p2-res[0])>0) swap(res[0],res[1]);res.pop_back();}return res;}Polygon getCrossPointCC(Circle c1,Circle c2){Polygon p(2);double d=abs(c1.c-c2.c);double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));double t=arg(c2.c-c1.c);p[0]=c1.c+polar(c1.r,t+a);p[1]=c1.c+polar(c1.r,t-a);return p;}// IN:2 ON:1 OUT:0Int contains(Polygon g,Point p){Int n=g.size();bool x=false;for(Int i=0;i<n;i++){Point a=g[i]-p,b=g[(i+1)%n]-p;if(fabs(cross(a,b)) < EPS && dot(a,b) < EPS) return 1;if(a.y>b.y) swap(a,b);if(a.y < EPS && EPS < b.y && cross(a,b) > EPS ) x = !x;}return (x?2:0);}Polygon andrewScan(Polygon s){Polygon u,l;if(s.size()<3) return s;sort(s.begin(),s.end());u.push_back(s[0]);u.push_back(s[1]);l.push_back(s[s.size()-1]);l.push_back(s[s.size()-2]);for(Int i=2;i<(Int)s.size();i++){for(Int n=u.size();n>=2&&ccw(u[n-2],u[n-1],s[i])!=CCW_CLOCKWISE;n--){u.pop_back();}u.push_back(s[i]);}for(Int i=s.size()-3;i>=0;i--){for(Int n=l.size();n>=2&&ccw(l[n-2],l[n-1],s[i])!=CCW_CLOCKWISE;n--){l.pop_back();}l.push_back(s[i]);}reverse(l.begin(),l.end());for(Int i=u.size()-2;i>=1;i--) l.push_back(u[i]);return l;}Polygon convex_hull(Polygon ps){Int n=ps.size();sort(ps.begin(),ps.end(),sort_y);Int k=0;Polygon qs(n*2);for(Int i=0;i<n;i++){while(k>1&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<0) k--;qs[k++]=ps[i];}for(Int i=n-2,t=k;i>=0;i--){while(k>t&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<0) k--;qs[k++]=ps[i];}qs.resize(k-1);return qs;}double diameter(Polygon s){Polygon p=s;Int n=p.size();if(n==2) return abs(p[0]-p[1]);Int i=0,j=0;for(Int k=0;k<n;k++){if(p[i]<p[k]) i=k;if(!(p[j]<p[k])) j=k;}double res=0;Int si=i,sj=j;while(i!=sj||j!=si){res=max(res,abs(p[i]-p[j]));if(cross(p[(i+1)%n]-p[i],p[(j+1)%n]-p[j])<0.0){i=(i+1)%n;}else{j=(j+1)%n;}}return res;}bool isConvex(Polygon p){bool f=1;Int n=p.size();for(Int i=0;i<n;i++){Int t=ccw(p[(i+n-1)%n],p[i],p[(i+1)%n]);f&=t!=CCW_CLOCKWISE;}return f;}double area(Polygon s){double res=0;for(Int i=0;i<(Int)s.size();i++){res+=cross(s[i],s[(i+1)%s.size()])/2.0;}return abs(res);}double area(Circle c1,Circle c2){double d=abs(c1.c-c2.c);if(c1.r+c2.r<=d+EPS) return 0;if(d<=abs(c1.r-c2.r)){double r=min(c1.r,c2.r);return PI*r*r;}double rc=(d*d+c1.r*c1.r-c2.r*c2.r)/(2*d);double th=acos(rc/c1.r);double ph=acos((d-rc)/c2.r);return c1.r*c1.r*th+c2.r*c2.r*ph-d*c1.r*sin(th);}Polygon convexCut(Polygon p,Line l){Polygon q;for(Int i=0;i<(Int)p.size();i++){Point a=p[i],b=p[(i+1)%p.size()];if(ccw(l.p1,l.p2,a)!=-1) q.push_back(a);if(ccw(l.p1,l.p2,a)*ccw(l.p1,l.p2,b)<0)q.push_back(getCrossPointLL(Line(a,b),l));}return q;}Line bisector(Point p1,Point p2){Circle c1=Circle(p1,abs(p1-p2)),c2=Circle(p2,abs(p1-p2));Polygon p=getCrossPointCC(c1,c2);if(cross(p2-p1,p[0]-p1)>0) swap(p[0],p[1]);return Line(p[0],p[1]);}Vector translate(Vector v,double theta){Vector res;res.x=cos(theta)*v.x-sin(theta)*v.y;res.y=sin(theta)*v.x+cos(theta)*v.y;return res;}vector<Line> corner(Line l1,Line l2){vector<Line> res;if(isParallel(l1,l2)){double d=getDistanceLP(l1,l2.p1)/2.0;Vector v1=l1.p2-l1.p1;v1=v1/v1.abs()*d;Point p=l2.p1+translate(v1,90.0*(PI/180.0));double d1=getDistanceLP(l1,p);double d2=getDistanceLP(l2,p);if(abs(d1-d2)>d){p=l2.p1+translate(v1,-90.0*(PI/180.0));}res.push_back(Line(p,p+v1));}else{Point p=getCrossPointLL(l1,l2);Vector v1=l1.p2-l1.p1,v2=l2.p2-l2.p1;v1=v1/v1.abs();v2=v2/v2.abs();res.push_back(Line(p,p+(v1+v2)));res.push_back(Line(p,p+translate(v1+v2,90.0*(PI/180.0))));}return res;}Polygon tangent(Circle c1,Point p2){Circle c2=Circle(p2,sqrt(norm(c1.c-p2)-c1.r*c1.r));Polygon p=getCrossPointCC(c1,c2);sort(p.begin(),p.end());return p;}vector<Line> tangent(Circle c1,Circle c2){vector<Line> ls;if(c1.r<c2.r) swap(c1,c2);double g=norm(c1.c-c2.c);if(equals(g,0)) return ls;Point u=(c2.c-c1.c)/sqrt(g);Point v=orth(u);for(Int s=1;s>=-1;s-=2){double h=(c1.r+s*c2.r)/sqrt(g);if(equals(1-h*h,0)){ls.emplace_back(c1.c+u*c1.r,c1.c+(u+v)*c1.r);}else if(1-h*h>0){Point uu=u*h,vv=v*sqrt(1-h*h);ls.emplace_back(c1.c+(uu+vv)*c1.r,c2.c-(uu+vv)*c2.r*s);ls.emplace_back(c1.c+(uu-vv)*c1.r,c2.c-(uu-vv)*c2.r*s);}}return ls;}double closest_pair(Polygon &a,Int l=0,Int r=-1){if(r<0){r=a.size();sort(a.begin(),a.end(),sort_x);}if(r-l<=1) return abs(a[0]-a[1]);Int m=(l+r)>>1;double x=a[m].x;double d=min(closest_pair(a,l,m),closest_pair(a,m,r));inplace_merge(a.begin()+l,a.begin()+m,a.begin()+r,sort_y);Polygon b;for(Int i=l;i<r;i++){if(fabs(a[i].x-x)>=d) continue;for(Int j=0;j<(Int)b.size();j++){double dy=a[i].y-next(b.rbegin(),j)->y;if(dy>=d) break;d=min(d,abs(a[i]-*next(b.rbegin(),j)));}b.emplace_back(a[i]);}return d;}vector<vector<pair<Int, double> > >segmentArrangement(vector<Segment> &ss, Polygon &ps){Int n=ss.size();for(Int i=0;i<n;i++){ps.emplace_back(ss[i].p1);ps.emplace_back(ss[i].p2);for(Int j=i+1;j<n;j++)if(intersectSS(ss[i],ss[j]))ps.emplace_back(getCrossPointSS(ss[i],ss[j]));}sort(ps.begin(),ps.end());ps.erase(unique(ps.begin(),ps.end()),ps.end());vector<vector<pair<Int, double> > > G(ps.size());for(Int i=0;i<n;i++){vector<pair<double,Int> > ls;for(Int j=0;j<(Int)ps.size();j++)if(getDistanceSP(ss[i],ps[j])<EPS)ls.emplace_back(make_pair(norm(ss[i].p1-ps[j]),j));sort(ls.begin(),ls.end());for(Int j=0;j+1<(Int)ls.size();j++){Int a=ls[j].second,b=ls[j+1].second;G[a].emplace_back(b,abs(ps[a]-ps[b]));G[b].emplace_back(a,abs(ps[a]-ps[b]));}}return G;}Int manhattanIntersection(vector<Segment> ss,const Int INF){const Int BTM = 0;const Int LFT = 1;const Int RGH = 2;const Int TOP = 3;Int n=ss.size();vector<EndPoint> ep;for(Int i=0;i<n;i++){if(ss[i].p1.y==ss[i].p2.y){if(ss[i].p1.x>ss[i].p2.x) swap(ss[i].p1,ss[i].p2);ep.emplace_back(ss[i].p1,i,LFT);ep.emplace_back(ss[i].p2,i,RGH);}else{if(ss[i].p1.y>ss[i].p2.y) swap(ss[i].p1,ss[i].p2);ep.emplace_back(ss[i].p1,i,BTM);ep.emplace_back(ss[i].p2,i,TOP);}}sort(ep.begin(),ep.end());set<Int> bt;bt.insert(INF);Int cnt=0;for(Int i=0;i<n*2;i++){if(ep[i].st==TOP){bt.erase(ep[i].p.x);}else if(ep[i].st==BTM){bt.emplace(ep[i].p.x);}else if(ep[i].st==LFT){auto b=bt.lower_bound(ss[ep[i].seg].p1.x);auto e=bt.upper_bound(ss[ep[i].seg].p2.x);cnt+=distance(b,e);}}return cnt;}double area(Polygon ps,Circle c){if(ps.size()<3u) return 0;function<double(Circle, Point, Point)> dfs=[&](Circle c,Point a,Point b){Vector va=c.c-a,vb=c.c-b;double f=cross(va,vb),res=0;if(equals(f,0.0)) return res;if(max(abs(va),abs(vb))<c.r+EPS) return f;Vector d(a.x*b.x+a.y*b.y,a.x*b.y-a.y*b.x);if(getDistanceSP(Segment(a,b),c.c)>c.r-EPS)return c.r*c.r*atan2(d.y,d.x);auto u=getCrossPointCS(c,Segment(a,b));if(u.empty()) return res;if(u.size()>1u&&dot(u[1]-u[0],a-u[0])>0) swap(u[0],u[1]);u.emplace(u.begin(),a);u.emplace_back(b);for(Int i=1;i<(Int)u.size();i++)res+=dfs(c,u[i-1],u[i]);return res;};double res=0;for(Int i=0;i<(Int)ps.size();i++)res+=dfs(c,ps[i],ps[(i+1)%ps.size()]);return res/2;}//INSERT ABOVE HEREInt is_tri(double a,double b,double c){if(a+b<c) return 0;if(a+c<b) return 0;if(b+c<a) return 0;return 1;}Int n;double a,b;Circle ca,cb;Int check(double x,Circle d,Int s,Int f=0){//cout<<x<<":"<<s<<" "<<n<<endl;if(s>=n) return 0;double p=a+x;double q=b-x;double r=b-a;if(!is_tri(p,q,r)) return 0;double th=acos((q*q+r*r-p*p)/(2*q*r));Vector v(-q,0);v=translate(v,-th);Circle c(v+cb.c,x);if(abs(c.c-d.c)<c.r+d.r) return 0;//cout<<c.c<<endl;if(f) return 1;Circle e=c;e.c.y*=-1;if(abs(c.c-e.c)<c.r+e.r) return 1;double L=x,R=b-a;if(!check(R,c,s+2,1)) return 2;for(Int k=0;k<200;k++){double M=(L+R)/2;if(check(M,c,s+2,1)) R=M;else L=M;}return check(R,c,s+2)+2;}signed main(){cin>>n>>a>>b;ca=Circle(Point(a,0),a);cb=Circle(Point(b,0),b);double l=0,r=b-a;for(Int k=0;k<200;k++){double m=(l+r)/2;if(check(m,Circle(Point(0,0),0),0)>=n) l=m;else r=m;}cout<<l<<endl;return 0;}