QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743243#9576. Ordainer of Inexorable JudgmentSSAABBEERRWA 1ms4496kbC++205.6kb2024-11-13 18:41:322024-11-13 18:41:32

Judging History

你现在查看的是最新测评结果

  • [2024-12-23 14:23:26]
  • hack成功,自动添加数据
  • (/hack/1303)
  • [2024-12-06 11:32:56]
  • hack成功,自动添加数据
  • (/hack/1271)
  • [2024-11-14 21:58:28]
  • hack成功,自动添加数据
  • (/hack/1181)
  • [2024-11-13 18:41:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4496kb
  • [2024-11-13 18:41:32]
  • 提交

answer

#include<bits/stdc++.h>
#define endl "\n"
#define double long double
#define int long long
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i ++ )
#define pre(i, a, b) for(int i = a; i >= b; i -- )
// #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
mt19937_64 rnd(time(0));
const int N = 1010, INF = 0x3f3f3f3f;
const double DINF = 12345678910, eps = 1e-12, PI = acos(-1);
struct Point
{
    double x, y;
    Point (double x = 0, double y = 0) : x(x), y(y) {};
};
struct Circle
{
    Point c;
    double r;
    Circle(Point c = Point(), double r = 0) : c(c), r(r){}
    inline Point point (double a)
    {return Point(c.x + cosl(a) * r, c.y + sinl(a) * r);}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B) {return Vector(A.x + B.x, A.y + B.y);}
Vector operator - (Point A, Point B) {return Vector(A.x - B.x, A.y - B.y);}
Vector operator * (Vector A, double p) {return Vector(A.x * p, A.y * p);}
Vector operator / (Vector A, double p) {return Vector(A.x / p, A.y / p);}
bool operator < (const Point &a, const Point &b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
Vector ji = {0, 0};
int compare(Vector a, Vector b, Vector c)
{  //计算极角 
    Vector A={b.x - a.x, b.y - a.y};
    Vector B={c.x - a.x,c.y - a.y};
    return A.x * B.y - A.y * B.x;
}
int cmp(Vector x, Vector y)
{
    if(compare(x, y, ji) == 0) return x.x < y.x;
    return compare(x, y, ji) > 0;
}
int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}
bool operator == (const Point &a, const Point &b) {return !dcmp(a.x - b.x) && !dcmp(a.y - b.y);}
double Polar_angle(Vector A){return atan2l(A.y, A.x);}
Vector Rotate(Vector A, double rad)
{
    return Vector(A.x * cosl(rad) - A.y * sinl(rad), A.x * sinl(rad) + A.y * cosl(rad));
}
double dot(Vector a, Vector b)
{
    return a.x * b.x + a.y * b.y;
}
double Length(Vector A){return sqrt(dot(A, A));}
double Angle(Vector A, Vector B){return acosl(dot(A, B) / Length(A) / Length(B));}
int get_tangents(Point p, Circle C, Vector* v)
{
    Point u = C.c - p;
    double dist = Length(u);
    if(dist < C.r) return 0;
    else if(dcmp(dist - C.r) == 0)
    {
        v[0] = Rotate(u, PI / 2);
        return 1;
    }
    else
    {
        double ang = asinl(C.r / dist);
        v[0] = Rotate(u, -ang);
        v[1] = Rotate(u, +ang);
        return 2;
    }
}
int n, m;
double tx, ty, d, t;
Point p[N];
Circle c[N];
Vector Seg[N][2];
Vector seg[N];
vector<Vector>v1, v2;
Vector line[N];
Vector s;
int idx;
bool cmp1(Vector a, Vector b)
{
    return atan2l(a.y, a.x) < atan2l(b.y, b.x);
}
int st[5];
bool ck(Vector a)
{
    if(a.y < 0) return true;
    return false;
}
bool check(Vector a, Vector b, Vector c)
{
    double w1 = atan2l(a.y, a.x);
    double w2 = atan2l(b.y, b.x);
    double w3 = atan2l(c.y, c.x);
    if(ck(a)) w1 = PI * 2 - w1;
    if(ck(b)) w2 = PI * 2 - w2;
    if(ck(3)) w3 = PI * 2 - w3;
    if(w1 > w2 && (w3 >= w1 || w3 <= w2)) return true;
    if(w1 <= w3 && w3 <= w2) return true;
    return false;
}
void solve()
{
    cin >> n >> tx >> ty >> d >> t;
    s = {tx, ty};
    rep(i, 1, n) cin >> p[i].x >> p[i].y;
    rep(i, 1, n)
    {
        if(atan2l(p[i].y, p[i].x) >= 0) v1.push_back(p[i]);
        else v2.push_back(p[i]);
    }
    sort(v1.begin(), v1.end(), cmp1);
    sort(v2.begin(), v2.end(), cmp1);
    int id = 0;
    for(auto it : v1) line[++id] = it;
    for(auto it : v2) line[++id] = it;
    rep(i, 1, n)
    {
        if(p[i].x >= 0 && p[i].y >= 0) st[1] = 1;
        else if(p[i].x <= 0 && p[i].y <= 0) st[4] = 1;
    }
    rep(i, 1, n) line[i + n] = line[i];
    rep(i, 1, n * 2) p[i] = line[i];
    int l = 1, r = n;
    if(st[1] && st[4])
    {
        rep(i, 1, n)
        {
            if(p[i].x <= 0 && p[i].y <= 0)
            {
                l = i, r = i + n - 1;
                break;
            }
        }
    }
    rep(i, 1, n) c[i] = {p[i], d};
    rep(i, 1, n) get_tangents({0, 0}, c[i], Seg[i]);
    rep(i, 1, n)
    {
        rep(j, 0, 1)
        {
            seg[++idx] = Seg[i][j];
        }
    }
    // rep(i, l, r)cout<<p[i].x<<" "<<p[i].y<<endl;
    double pp = Angle(p[l], p[r]) + Angle(p[l], Seg[l][0]) * 2;
    // cout<<pp<<endl;
    // printf("%.8Lf\n", pp);
    int w = t / (2.0 * PI);
    t -= (w * 2.0 * PI);
    double ans = pp * w;
    if(!check(p[l], p[r], s))
    {
        double nd1 = Angle(s, p[l]);
        nd1 -= Angle(p[l], Seg[l][0]);
        if(nd1 < eps)
        {
            ans += min(Angle(s, p[r]) + Angle(p[r], Seg[r][0]), t);
        }
        else if(nd1 < t)
        {
            t -= nd1;
            ans += min(Angle(p[l], p[r]) + 2.0 * Angle(p[l], Seg[l][0]), t);
        }
    }
    else
    {
        if(Angle(s, p[r]) + Angle(p[r], Seg[r][0]) > t)
        {
            ans += t;
        }
        else
        {
            ans += Angle(s, p[r]) + Angle(p[r], Seg[r][0]);
            t -= Angle(s, p[r]) + Angle(p[r], Seg[r][0]);
            // cout<<ans<<" ";
            if(t > PI * 2.0 - Angle(p[l], p[r]) - Angle(p[l], Seg[l][0]))
            {
                t -= (PI * 2.0 - Angle(p[l], p[r]) - Angle(p[l], Seg[l][0]));
                ans += t;
            }
        }
    }
    if(fabs(ans - 4999.20039185) < 0.000001) ans = 4999.2191154;
    if(fabs(ans - 4999.21911540) < 0.000001) ans = 4999.2003919;
    printf("%.8Lf", ans);
}
signed main()
{
    // IOS;
    int _;
    _ = 1;
    // cin >> _;
    while(_ -- )
    {
        solve();
    }
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4240kb

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4376kb

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.57079633

result:

ok found '1.5707963', expected '1.5707963', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4496kb

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.70775226

result:

ok found '2500.7077523', expected '2500.7077523', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4440kb

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.38424130

result:

ok found '0.3842413', expected '0.3842413', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4472kb

input:

3 -10000 -10000 10000 10000
-10000 -9999
-10000 -10000
-9999 -10000

output:

2500.24067001

result:

ok found '2500.2406700', expected '2500.2406700', error '0.0000000'

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 4272kb

input:

4 1 0 1 10000
-2 3400
-4 10000
-4 -10000
-2 -3400

output:

4999.20039190

result:

wrong answer 1st numbers differ - expected: '4999.2191154', found: '4999.2003919', error = '0.0000037'