QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#773169 | #9576. Ordainer of Inexorable Judgment | Arnold_6 | WA | 0ms | 4260kb | C++17 | 8.2kb | 2024-11-23 02:41:48 | 2024-11-23 02:41:49 |
Judging History
你现在查看的是最新测评结果
- [2024-12-23 14:23:26]
- hack成功,自动添加数据
- (/hack/1303)
- [2024-12-06 11:32:56]
- hack成功,自动添加数据
- (/hack/1271)
- [2024-11-23 02:41:48]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
#define db long double
// using point_t=long long;
using point_t=long double; //全局数据类型
constexpr point_t eps=1e-12;
constexpr point_t INF=numeric_limits<point_t>::max();
constexpr long double PI=3.1415926535897932384l;
// 点与向量
template<typename T> struct point
{
T x,y;
bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
bool operator<(const point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
bool operator>(const point &a) const {return !(*this<a || *this==a);}
point operator+(const point &a) const {return {x+a.x,y+a.y};}
point operator-(const point &a) const {return {x-a.x,y-a.y};}
point operator-() const {return {-x,-y};}
point operator*(const T k) const {return {k*x,k*y};}
point operator/(const T k) const {return {x/k,y/k};}
T operator*(const point &a) const {return x*a.x+y*a.y;} // 点积
T operator^(const point &a) const {return x*a.y-y*a.x;} // 叉积,注意优先级
int toleft(const point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);} // to-left 测试
T len2() const {return (*this)*(*this);} // 向量长度的平方
T dis2(const point &a) const {return (a-(*this)).len2();} // 两点距离的平方
// 涉及浮点数
long double len() const {return sqrtl(len2());} // 向量长度
long double dis(const point &a) const {return sqrtl(dis2(a));} // 两点距离
long double ang(const point &a) const {return acosl(max(-1.0l,min(1.0l,((*this)*a)/(len()*a.len()))));} // 向量夹角
point rot(const long double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};} // 逆时针旋转(给定角度)
point rot(const long double cosr,const long double sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};} // 逆时针旋转(给定角度的正弦与余弦)
};
using Point=point<point_t>;
// 极角排序
struct argcmp
{
bool operator()(const Point &a,const Point &b) const
{
// const auto quad=[](const Point &a)
// {
// if (a.y<-eps) return 1;
// if (a.y>eps) return 4;
// if (a.x<-eps) return 5;
// if (a.x>eps) return 3;
// return 2;
// };
// const int qa=quad(a),qb=quad(b);
// if (qa!=qb) return qa<qb;
const auto t=a^b;
// if (abs(t)<=eps) return a*a<b*b-eps; // 不同长度的向量需要分开
return t>eps;
}
};
// 直线
template<typename T> struct line
{
point<T> p,v; // p 为直线上一点,v 为方向向量
bool operator==(const line &a) const {return v.toleft(a.v)==0 && v.toleft(p-a.p)==0;}
int toleft(const point<T> &a) const {return v.toleft(a-p);} // to-left 测试
bool operator<(const line &a) const // 半平面交算法定义的排序
{
if (abs(v^a.v)<=eps && v*a.v>=-eps) return toleft(a.p)==-1;
return argcmp()(v,a.v);
}
// 涉及浮点数
point<T> inter(const line &a) const {return p+v*((a.v^(p-a.p))/(v^a.v));} // 直线交点
long double dis(const point<T> &a) const {return abs(v^(a-p))/v.len();} // 点到直线距离
point<T> proj(const point<T> &a) const {return p+v*((v*(a-p))/(v*v));} // 点在直线上的投影
};
using Line=line<point_t>;
//线段
template<typename T> struct segment
{
point<T> a,b;
bool operator<(const segment &s) const {return make_pair(a,b)<make_pair(s.a,s.b);}
// 判定性函数建议在整数域使用
// 判断点是否在线段上
// -1 点在线段端点 | 0 点不在线段上 | 1 点严格在线段上
int is_on(const point<T> &p) const
{
if (p==a || p==b) return -1;
return (p-a).toleft(p-b)==0 && (p-a)*(p-b)<-eps;
}
// 判断线段直线是否相交
// -1 直线经过线段端点 | 0 线段和直线不相交 | 1 线段和直线严格相交
int is_inter(const line<T> &l) const
{
if (l.toleft(a)==0 || l.toleft(b)==0) return -1;
return l.toleft(a)!=l.toleft(b);
}
// 判断两线段是否相交
// -1 在某一线段端点处相交 | 0 两线段不相交 | 1 两线段严格相交
int is_inter(const segment<T> &s) const
{
if (is_on(s.a) || is_on(s.b) || s.is_on(a) || s.is_on(b)) return -1;
const line<T> l{a,b-a},ls{s.a,s.b-s.a};
return l.toleft(s.a)*l.toleft(s.b)==-1 && ls.toleft(a)*ls.toleft(b)==-1;
}
// 点到线段距离
long double dis(const point<T> &p) const
{
if ((p-a)*(b-a)<-eps || (p-b)*(a-b)<-eps) return min(p.dis(a),p.dis(b));
const line<T> l{a,b-a};
return l.dis(p);
}
// 两线段间距离
long double dis(const segment<T> &s) const
{
if (is_inter(s)) return 0;
return min({dis(s.a),dis(s.b),s.dis(a),s.dis(b)});
}
};
using Segment=segment<point_t>;
// 多边形
template<typename T> struct polygon
{
vector<point<T>> p; // 以逆时针顺序存储
size_t nxt(const size_t i) const {return i==p.size()-1?0:i+1;}
size_t pre(const size_t i) const {return i==0?p.size()-1:i-1;}
};
using Polygon=polygon<point_t>;
//凸多边形
template<typename T> struct convex: polygon<T>
{};
using Convex=convex<point_t>;
// 圆
struct Circle
{
Point c;
long double r;
bool operator==(const Circle &a) const {return c==a.c && abs(r-a.r)<=eps;}
long double circ() const {return 2*PI*r;} // 周长
long double area() const {return PI*r*r;} // 面积
// 过圆外一点圆的切线
vector<Line> tangent(const Point &a) const
{
Point e=a-c; e=e/e.len()*r;
const long double costh=r/c.dis(a),sinth=sqrt(1-costh*costh);
const Point t1=c+e.rot(costh,-sinth),t2=c+e.rot(costh,sinth);
return vector<Line>{{a,t1-a},{a,t2-a}};
}
};
int main()
{
// Point a{1.0,0},b{-1.0,sqrt(3)};cout<<a.ang(b)<<endl;
int n;
db x0,y0,d,t;
cin>>n>>x0>>y0>>d>>t;
Point st={x0,y0};
Polygon poly;
Circle c{{0.0,0.0},d};
for(int i=1;i<=n;i++)
{
db x,y;
cin>>x>>y;
poly.p.push_back({x,y});
}
Polygon pp;
for(auto p:poly.p)
{
vector<Line> tmp=c.tangent(p);
Point v1=-tmp[0].v,v2=-tmp[1].v;
pp.p.push_back(v1);
pp.p.push_back(v2);
}
sort(pp.p.begin(),pp.p.end(),argcmp());
// for(auto i:pp.p)
// {
// cout<<i.x<<" "<<i.y<<endl;
// }
db tt=pp.p[0].ang(pp.p[pp.p.size()-1]);
// cout<<tt<<endl;
Point p1=pp.p[0],p2=pp.p[pp.p.size()-1];
// if((p1^p2)<0)swap(p1,p2);
db ans=0;
int times=0;
if(t-2*PI>=eps)
{
times=t/2.0/PI;
ans=times*tt;
t=t-2.0*PI*times;
}
if(t<=eps)
{
cout<<ans;
return 0;
}
// cout<<times<<" "<<fixed<<setprecision(15)<<t<<" "<<ans<<endl;
Point ed=st.rot(t);
// cout<<ed.x<<" "<<ed.y<<endl;
// cout<<p1.x<<" "<<p1.y<<endl;
// cout<<p2.x<<" "<<p2.y<<endl;
// cout<<p1.toleft(ed)<<" "<<p2.toleft(ed)<<endl;
if((p1.toleft(st))>=0 && (p2.toleft(st))<0 )
{
if(st.toleft(ed)>=0)
{
if((p1.toleft(ed))>=0 && (p2.toleft(ed))<=0)
{
ans+=st.ang(ed);
}
else
{
ans+=st.ang(p2);
}
}
else
{
if((p1.toleft(ed))>=0 && (p2.toleft(ed))<=0)
{
ans+=st.ang(p2)+p1.ang(ed);
}
else
{
ans+=st.ang(p2);
}
}
}
else
{
if((p1.toleft(ed))>=0 && (p2.toleft(ed))<=0)
{
ans+=p1.ang(ed);
}
else
{
db ang=st.ang(ed);
if(st.toleft(ed)<0 || fabs(st*ed+1)<=eps)
{
ang=2*PI-ang;
}
if(ang-tt>=eps)ans+=tt;
else ans+=p1.ang(ed);
}
}
cout<<fixed<<setprecision(15)<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4200kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.000000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.570796326794897
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4176kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.707752257475418
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4224kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.384241300289928
result:
ok found '0.3842413', expected '0.3842413', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4220kb
input:
3 -10000 -10000 10000 10000 -10000 -9999 -10000 -10000 -9999 -10000
output:
2500.240670009608470
result:
ok found '2500.2406700', expected '2500.2406700', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4220kb
input:
4 1 0 1 10000 -2 3400 -4 10000 -4 -10000 -2 -3400
output:
4999.219115408742558
result:
ok found '4999.2191154', expected '4999.2191154', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4260kb
input:
4 1 0 1 10000 -2 3300 -4 10000 -4 -10000 -2 -3300
output:
4999.200391854814572
result:
ok found '4999.2003919', expected '4999.2003919', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4168kb
input:
4 -3040 2716 2147 2 -9033 -8520 -8999 -8533 -8988 -8511 -9004 -8495
output:
0.350830058342073
result:
ok found '0.3508301', expected '0.3508301', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4168kb
input:
3 8168 -766 1549 1256 -3951 -6425 -3874 -6439 -3911 -6389
output:
84.832861161006953
result:
ok found '84.8328612', expected '84.8328612', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4256kb
input:
8 2977 -3175 8766 2 -4868 7759 -4867 7925 -4867 7950 -4886 7952 -4979 7953 -5048 7877 -5003 7761 -4936 7759
output:
0.327860646906109
result:
ok found '0.3278606', expected '0.3278606', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 4204kb
input:
13 -1715 -4640 267 8651 272 6659 264 6660 208 6664 108 6625 107 6621 93 6564 90 6551 90 6485 124 6474 219 6477 283 6525 288 6591 286 6657
output:
153.589622784682281
result:
ok found '153.5896228', expected '153.5896228', error '0.0000000'
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 4076kb
input:
8 -9743 -7629 775 7 -194 981 -191 1720 -193 1845 -705 1929 -959 1950 -1131 1894 -1151 1604 -1031 1020
output:
4.685798347272487
result:
wrong answer 1st numbers differ - expected: '2.0460062', found: '4.6857983', error = '1.2902171'