結果
| 問題 | No.1178 Can you draw a Circle? |
| ユーザー |
 mugen_1337
|
| 提出日時 | 2020-08-21 21:26:47 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 13,784 bytes |
| コンパイル時間 | 3,510 ms |
| コンパイル使用メモリ | 228,684 KB |
| 最終ジャッジ日時 | 2025-01-13 05:03:21 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 5 WA * 10 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
struct IOSetup{
IOSetup(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(12);
}
} iosetup;
template<typename T1,typename T2>
ostream &operator<<(ostream &os,const pair<T1,T2>&p){
os<<p.first<<" "<<p.second;
return os;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
return os;
}
template<typename T1,typename T2>
istream &operator>>(istream &is,pair<T1,T2>&p){
is>>p.first>>p.second;
return is;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
for(T &x:v)is>>x;
return is;
}
//////////////////////////////////////////////////////
using Real=double;
using Point=complex<Real>;
const Real EPS=1e-10;
const Real pi=acosl(-1);
//入出力補助
istream &operator>>(istream &is,Point &p){
Real a,b;
is>>a>>b;
p=Point(a,b);
return is;
}
ostream &operator<<(ostream &os,Point &p){
return os<<fixed<<setprecision(12)<<p.real()<<' '<<p.imag();
}
inline bool eq(Real a,Real b){
return fabs(a-b)<EPS;
}
Point operator*(const Point &p,const Real &d){
return Point(real(p)*d,imag(p)*d);
}
struct Line{
Point p1,p2;
Line()=default;
Line(Point p1,Point p2):p1(p1),p2(p2){}
//Ax + By = C
Line(Real A,Real B,Real C){
if(eq(A,0)) p1=Point(0,C/B),p2=Point(1,C/B);
else if(eq(B,0))p1=Point(C/A,0),p2=Point(C/A,1);
else p1=Point(0,C/B),p2=Point(C/A,0);
}
};
struct Segment:Line{
Segment()=default;
Segment(Point p1,Point p2):Line(p1,p2){}
};
struct Circle{
Point center;
Real r;
Circle()=default;
Circle(Point center,Real r):center(center),r(r){}
};
/////////////////////////////////////////////////////////
// 点 p を反時計回りに theta 回転
Point rotate(Real theta,const Point &p) {
return Point(cos(theta)*p.real()-sin(theta)*p.imag(),sin(theta)*p.real()+cos(theta)*p.imag());
}
Real radian_to_degree(Real r){
return r*180.0/pi;
}
Real degree_to_radian(Real d){
return d*pi/180.0;
}
//三角形の面積，サラスの公式
Real area_triangle(Point a,Point b,Point c){
Point x=b-a,y=c-a;
return fabs(x.real()*y.imag()-x.imag()*y.real())/2;
}
//v
//外積
Real cross(Point a,Point b){
return real(a)*imag(b)-imag(a)*real(b);
}
//v
//内積
Real dot(Point a,Point b) {
return real(a)*real(b)+imag(a)*imag(b);
}
//v
//平行判定，外積0かをみる
bool parallel(Line a,Line b){
return eq(cross(a.p1-a.p2,b.p1-b.p2),0.0);
}
//v
//垂直判定，内積0かをみる
bool orthogonal(Line a,Line b){
return eq(dot(a.p1-a.p2,b.p1-b.p2),0.0);
}
//v
//正射影，pからlに下した垂線の足を求める
Point projection(Line l,Point p){
//ベクトルl上のどの位置に垂線の足が来るか求める
Real k=dot(l.p1-l.p2,p-l.p1)/norm(l.p1-l.p2);
return l.p1+(l.p1-l.p2)*k;
}
Point projection(Segment l,Point p){
Real k=dot(l.p1-l.p2,p-l.p1)/norm(l.p1-l.p2);
return l.p1+(l.p1-l.p2)*k;
}
//v
//反射，直線lに関し点pと線対称な点を返す
Point reflection(Line l,Point p){
Point h=projection(l,p);
return (p+(h-p)+(h-p));
}
Point reflection(Segment l,Point p){
Point h=projection(l,p);
return (p+(h-p)+(h-p));
}
//二点間の距離
Real dis(Point a,Point b){
return abs(a-b);
}
//点と直線の距離
Real dis(Line l,Point p){
return abs(p-projection(l,p));
}
//v
//COUNTER CLOCKWISE，返す値は↓を参照
//https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_1_C
int ccw(Point a,Point b,Point c){
b-=a;c-=a;
if(cross(b,c)>EPS) return 1;//COUNTER CLOCKWISE
else if(cross(b,c)<-EPS) return -1;//CLOCKWISE
else if(dot(b,c)<0) return 2;//c--a--b ONLINE BACK
else if(norm(b)<norm(c)) return -2;//a--b--c ONLINE FRONT
else return 0;//a--c--b ON SEGMENT
}
//v
//3点が作る三角形の外心
//面積0の三角形を渡すと分母に面積があるので壊れるかも
Point circumcenter(Point A,Point B,Point C){
Real S=area_triangle(A,B,C);
Real a=dis(B,C),b=dis(A,C),c=dis(A,B);
return A*(a*a*(b*b+c*c-a*a)/(16*S*S))+B*(b*b*(c*c+a*a-b*b)/(16*S*S))+C*(c*c*(a*a+b*b-c*c)/(16*S*S));
}
//交差判定
//直線状に乗るか
bool intersect(Line l,Point p){
return abs(ccw(l.p1,l.p2,p))!=1;
}
//直線の交差判定，外積
bool intersect(Line l1,Line l2){
return abs(cross(l1.p2-l1.p1,l2.p2-l2.p1))>EPS or
abs(cross(l1.p2-l1.p1,l2.p2-l1.p1))<EPS;
}
//線分に点が乗るかの判定，ccw
bool intersect(Segment s,Point p){
return ccw(s.p1,s.p2,p)==0;
}
//直線と線分の交差判定
bool intersect(Line l,Segment s){
return cross(l.p2-l.p1,s.p1-l.p1)*cross(l.p2-l.p1,s.p2-l.p1)<EPS;
}
//円と直線の交差判定
bool intersect(Circle c,Line l){
return dis(l,c.center)<=c.r+EPS;
}
//円上かどうか，内部かどうかではない
bool intersect(Circle c,Point p){
return abs(abs(p-c.center)-c.r)<EPS;
}
//v
//線分と線分の交差判定
bool intersect(Segment s,Segment t){
return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <=0 and
ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0;
}
//線分と円の交差判定，交点の個数を返す
int intersect(Circle c,Segment l){
Point h=projection(l,c.center);
//直線まるっと円の外側
if(norm(h-c.center)-c.r*c.r>EPS) return 0;
Real d1=abs(c.center-l.p1),d2=abs(c.center-l.p2);
//線分が円内
if(d1<c.r+EPS and d2<c.r+EPS) return 0;
if((d1<c.r-EPS and d2>c.r+EPS) or (d2<c.r-EPS and d1>c.r+EPS)) return 1;
//円の外部にまるまるはみ出ていないか
if(dot(l.p1-h,l.p2-h)<0) return 2;
return 0;
}
//円と円の位置関係，共通接線の個数を返す
int intersect(Circle c1,Circle c2){
if(c1.r<c2.r) swap(c1,c2);
Real d=abs(c1.center-c2.center);
//2円が離れている
if(c1.r+c2.r<d) return 4;
//2円が外接する
if(eq(c1.r+c2.r,d)) return 3;
//2円が交わる
if(c1.r-c2.r<d) return 2;
//円が内接する
if(eq(c1.r-c2.r,d)) return 1;
//内包
return 0;
}
//交点
//線分の交点はintersectをチェックしてokなら直線の交点をやる
//intersectをチェックすること
//v
Point crosspoint(Line l,Line m){
Real A=cross(m.p2-m.p1,m.p1-l.p1);
Real B=cross(m.p2-m.p1,l.p2-l.p1);
if(eq(A,0) and eq(B,0)) return l.p1;
if(eq(B,0)) throw "NAI";
return l.p1+A/B*(l.p2-l.p1);
}
Point crosspoint(Segment l,Segment m){
return crosspoint(Line(l),Line(m));
}
vector<Point> crosspoint(Circle c,Line l){
vector<Point> ret;
Point h=projection(l,c.center);
Real d=sqrt(c.r*c.r-norm(h-c.center));
Point e=(l.p2-l.p1)*(1/abs(l.p2-l.p1));
if(c.r*c.r+EPS<norm(h-c.center)) return ret;
if(eq(dis(l,c.center),c.r)){
ret.push_back(h);
return ret;
}
ret.push_back(h+e*d);ret.push_back(h-e*d);
return ret;
}
//要verify，
vector<Point> crosspoint(Circle c,Segment s){
Line l=Line(s.p1,s.p2);
int ko=intersect(c,s);
if(ko==2) return crosspoint(c,l);
vector<Point> ret;
if(ko==0) return ret;
ret=crosspoint(c,l);
if(ret.size()==1) return ret;
vector<Point> rret;
//交点で挟める方を返す
if(dot(s.p1-ret[0],s.p2-ret[0])<0) rret.push_back(ret[0]);
else rret.push_back(ret[1]);
return rret;
}
//v
vector<Point> crosspoint(Circle c1,Circle c2){
vector<Point> ret;
int isec=intersect(c1,c2);
if(isec==0 or isec==4) return ret;
Real d=abs(c1.center-c2.center);
Real a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
Real t=atan2(c2.center.imag()-c1.center.imag(),c2.center.real()-c1.center.real());
ret.push_back(c1.center+Point(cos(t+a)*c1.r,sin(t+a)*c1.r));
ret.push_back(c1.center+Point(cos(t-a)*c1.r,sin(t-a)*c1.r));
return ret;
}
//v
//点pから引いた円cの接線の接点を返す
vector<Point> tangent(Circle c,Point p){
return crosspoint(c,Circle(p,sqrt(norm(c.center-p)-c.r*c.r)));
}
//v
//二円の共通接線，Lineの2点は接点を表す
vector<Line> tangent(Circle c1,Circle c2){
vector<Line> ret;
if(c1.r<c2.r) swap(c1,c2);
Real g=norm(c1.center-c2.center);
//中心が一致するならない
if(eq(g,0)) return ret;
Point u=(c2.center-c1.center)/sqrt(g);
Point v=rotate(pi*0.5,u);
for(int s:{-1,1}){
Real h=(c1.r+s*c2.r)/sqrt(g);
if(eq(1-h*h,0)){
ret.push_back(Line(c1.center+u*c1.r,c1.center+(u+v)*c1.r));
}
else if(1-h*h>0){
Point uu=u*h,vv=v*sqrt(1-h*h);
ret.push_back(Line(c1.center+(uu+vv)*c1.r,c2.center-(uu+vv)*c2.r*s));
ret.push_back(Line(c1.center+(uu-vv)*c1.r,c2.center-(uu-vv)*c2.r*s));
}
}
return ret;
}
//v
//最小包含円を返す 計算量は期待値O(n)
Circle MinimumBoundingCircle(vector<Point> v){
int n=v.size();
//ランダムシャッフル．いぢわるされたくないもんだ
mt19937 mt(time(0));
shuffle(v.begin(),v.end(),mt);
Circle ret(0,0);
//2点で円を作る
auto make_circle2=[&](Point a,Point b){
return Circle((a+b)*0.5,dis(a,b)/2);
};
//3点で円を作る
auto make_circle3=[&](Point A,Point B,Point C){
Point cent=circumcenter(A,B,C);
return Circle(cent,dis(cent,A));
};
auto isIn=[&](Point a){
return dis(ret.center,a)<ret.r+EPS;
};
ret=make_circle2(v[0],v[1]);
for(int i=2;i<n;i++){
//v[i]が円に入っていないなら
if(!isIn(v[i])){
//円内にないなら点v[i]は必ず円周上に来る
ret=make_circle2(v[0],v[i]);
for(int j=1;j<i;j++){
if(!isIn(v[j])){
//この時iとjが円周上を考える
ret=make_circle2(v[i],v[j]);
//最後の1点の決定
for(int k=0;k<j;k++){
if(!isIn(v[k])){
ret=make_circle3(v[i],v[j],v[k]);
}
}
}
}
}
}
return ret;
}
// v
// 最近点対
Real closest_pair(vector<Point> ps){
sort(ALL(ps),[&](Point a,Point b){
return real(a)<real(b);
});
function<Real(int,int)> rec=[&](int l,int r){
if(r-l<=1) return 1e18;
int m=(l+r)/2;
Real x=real(ps[m]);
Real ret=min(rec(l,m),rec(m,r));
inplace_merge(begin(ps)+l,begin(ps)+m,begin(ps)+r,[&](Point a,Point b){
return imag(a)<imag(b);
});
// 分割を跨いで最小距離があるか調べる
vector<Point> b;
for(int i=l;i<r;i++){
if(abs(real(ps[i])-x)>=ret) continue;
for(int j=(int)b.size()-1;j>=0;j--){
if(abs(imag(ps[i]-b[j]))>=ret) break;
ret=min(ret,abs(ps[i]-b[j]));
}
b.push_back(ps[i]);
}
return ret;
};
return rec(0,(int)ps.size());
}
// 凸多角形系統
// 凸多角形の頂点は反時計周りに訪れる順序
// v
// 頂点は反時計周りに訪れる順序，時計回りとなるような3点があるとfalse
bool is_convex(const vector<Point> &ps){
int n=(int)ps.size();
for(int i=0;i<n;i++)if(ccw(ps[(i+n-1)%n],ps[i],ps[(i+1)%n])==-1)return false;
return true;
}
// 凸包，あんまりよくわかってない．直線状に頂点をのせない場合(↑)，のせる場合(↓)
vector<Point> convex_hull(vector<Point> p){
int n=(int)p.size(),k=0;
if(n<=2)return p;
sort(begin(p),end(p),[](Point a,Point b){
return real(a)!=real(b)?real(a)<real(b):imag(a)<imag(b);
});
vector<Point>ch(2*n);
for(int i=0;i<n;ch[k++]=p[i++]){
// while(k>=2 and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<EPS)k--;
while(k>=2 and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<0)k--;
}
for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--]){
// while(k>=t and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<EPS)k--;
while(k>=t and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<0)k--;
}
ch.resize(k-1);
return ch;
}
// v 整数で凸法
using P=pair<int,int>;
vector<P> convex_hull(vector<P> p){
int n=(int)p.size(),k=0;
if(n<=2)return p;
sort(begin(p),end(p));
vector<P> ch(2*n);
auto crf=[&](P u,P v){return u.first*v.second-u.second*v.first;};
auto dff=[&](P u,P v){return make_pair(u.first-v.first,u.second-v.second);};
for(int i=0;i<n;ch[k++]=p[i++]){
while(k>=2 and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<0)k--;
// while(k>=2 and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<=0)k--;
}
for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--]){
while(k>=t and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<0)k--;
// while(k>=t and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<=0)k--;
}
ch.resize(k-1);
return ch;
}
signed main(){
Real a,b,c,d,e,f;cin>>a>>b>>c>>d>>e>>f;
cout<<sqrt(c*c/4/a+d*d/4/b+f-e)<<endl;
return 0;
}