QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#826661	#9869. Horizon Scanning	Traveler	WA	97ms	4248kb	C++20	10.4kb	2024-12-22 15:08:13	2024-12-22 15:08:14

Judging History

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

[2024-12-22 15:08:14]
评测

测评结果：WA
用时：97ms
内存：4248kb

查看

[2024-12-22 15:08:13]
提交

answer

// #include<bits/stdc++.h>
// using namespace std;
// using i64 = long long;
// template<class T>
// constexpr T power(T a, i64 b) {
//     T res = 1;
//     for (; b; b /= 2, a *= a) {
//         if (b % 2) {
//             res *= a;
//         }
//     }
//     return res;
// }

// constexpr i64 mul(i64 a, i64 b, i64 p) {
//     i64 res = a * b - i64(1.L * a * b / p) * p;
//     res %= p;
//     if (res < 0) {
//         res += p;
//     }
//     return res;
// }
// template<i64 P>
// struct MLong {
//     i64 x;
//     constexpr MLong() : x{} {}
//     constexpr MLong(i64 x) : x{norm(x % getMod())} {}
    
//     static i64 Mod;
//     constexpr static i64 getMod() {
//         if (P > 0) {
//             return P;
//         } else {
//             return Mod;
//         }
//     }
//     constexpr static void setMod(i64 Mod_) {
//         Mod = Mod_;
//     }
//     constexpr i64 norm(i64 x) const {
//         if (x < 0) {
//             x += getMod();
//         }
//         if (x >= getMod()) {
//             x -= getMod();
//         }
//         return x;
//     }
//     constexpr i64 val() const {
//         return x;
//     }
//     explicit constexpr operator i64() const {
//         return x;
//     }
//     constexpr MLong operator-() const {
//         MLong res;
//         res.x = norm(getMod() - x);
//         return res;
//     }
//     constexpr MLong inv() const {
//         assert(x != 0);
//         return power(*this, getMod() - 2);
//     }
//     constexpr MLong &operator*=(MLong rhs) & {
//         x = mul(x, rhs.x, getMod());
//         return *this;
//     }
//     constexpr MLong &operator+=(MLong rhs) & {
//         x = norm(x + rhs.x);
//         return *this;
//     }
//     constexpr MLong &operator-=(MLong rhs) & {
//         x = norm(x - rhs.x);
//         return *this;
//     }
//     constexpr MLong &operator/=(MLong rhs) & {
//         return *this *= rhs.inv();
//     }
//     friend constexpr MLong operator*(MLong lhs, MLong rhs) {
//         MLong res = lhs;
//         res *= rhs;
//         return res;
//     }
//     friend constexpr MLong operator+(MLong lhs, MLong rhs) {
//         MLong res = lhs;
//         res += rhs;
//         return res;
//     }
//     friend constexpr MLong operator-(MLong lhs, MLong rhs) {
//         MLong res = lhs;
//         res -= rhs;
//         return res;
//     }
//     friend constexpr MLong operator/(MLong lhs, MLong rhs) {
//         MLong res = lhs;
//         res /= rhs;
//         return res;
//     }
//     friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
//         i64 v;
//         is >> v;
//         a = MLong(v);
//         return is;
//     }
//     friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
//         return os << a.val();
//     }
//     friend constexpr bool operator==(MLong lhs, MLong rhs) {
//         return lhs.val() == rhs.val();
//     }
//     friend constexpr bool operator!=(MLong lhs, MLong rhs) {
//         return lhs.val() != rhs.val();
//     }
// };

// template<>
// i64 MLong<0LL>::Mod = i64(1E18) + 9;

// template<int P>
// struct MInt {
//     int x;
//     constexpr MInt() : x{} {}
//     constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
//     static int Mod;
//     constexpr static int getMod() {
//         if (P > 0) {
//             return P;
//         } else {
//             return Mod;
//         }
//     }
//     constexpr static void setMod(int Mod_) {
//         Mod = Mod_;
//     }
//     constexpr int norm(int x) const {
//         if (x < 0) {
//             x += getMod();
//         }
//         if (x >= getMod()) {
//             x -= getMod();
//         }
//         return x;
//     }
//     constexpr int val() const {
//         return x;
//     }
//     explicit constexpr operator int() const {
//         return x;
//     }
//     constexpr MInt operator-() const {
//         MInt res;
//         res.x = norm(getMod() - x);
//         return res;
//     }
//     constexpr MInt inv() const {
//         assert(x != 0);
//         return power(*this, getMod() - 2);
//     }
//     constexpr MInt &operator*=(MInt rhs) & {
//         x = 1LL * x * rhs.x % getMod();
//         return *this;
//     }
//     constexpr MInt &operator+=(MInt rhs) & {
//         x = norm(x + rhs.x);
//         return *this;
//     }
//     constexpr MInt &operator-=(MInt rhs) & {
//         x = norm(x - rhs.x);
//         return *this;
//     }
//     constexpr MInt &operator/=(MInt rhs) & {
//         return *this *= rhs.inv();
//     }
//     friend constexpr MInt operator*(MInt lhs, MInt rhs) {
//         MInt res = lhs;
//         res *= rhs;
//         return res;
//     }
//     friend constexpr MInt operator+(MInt lhs, MInt rhs) {
//         MInt res = lhs;
//         res += rhs;
//         return res;
//     }
//     friend constexpr MInt operator-(MInt lhs, MInt rhs) {
//         MInt res = lhs;
//         res -= rhs;
//         return res;
//     }
//     friend constexpr MInt operator/(MInt lhs, MInt rhs) {
//         MInt res = lhs;
//         res /= rhs;
//         return res;
//     }
//     friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
//         i64 v;
//         is >> v;
//         a = MInt(v);
//         return is;
//     }
//     friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
//         return os << a.val();
//     }
//     friend constexpr bool operator==(MInt lhs, MInt rhs) {
//         return lhs.val() == rhs.val();
//     }
//     friend constexpr bool operator!=(MInt lhs, MInt rhs) {
//         return lhs.val() != rhs.val();
//     }
// };

// template<>
// int MInt<0>::Mod = 998244353;

// template<int V, int P>
// constexpr MInt<P> CInv = MInt<P>(V).inv();

// constexpr int P = 1e9+7;
// using Z = MInt<P>;

// struct Comb {
//     int n;
//     std::vector<Z> _fac;
//     std::vector<Z> _invfac;
//     std::vector<Z> _inv;
    
//     Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
//     Comb(int n) : Comb() {
//         init(n);
//     }
    
//     void init(int m) {
//         m = std::min(m, Z::getMod() - 1);
//         if (m <= n) return;
//         _fac.resize(m + 1);
//         _invfac.resize(m + 1);
//         _inv.resize(m + 1);
        
//         for (int i = n + 1; i <= m; i++) {
//             _fac[i] = _fac[i - 1] * i;
//         }
//         _invfac[m] = _fac[m].inv();
//         for (int i = m; i > n; i--) {
//             _invfac[i - 1] = _invfac[i] * i;
//             _inv[i] = _invfac[i] * _fac[i - 1];
//         }
//         n = m;
//     }
    
//     Z fac(int m) {
//         if (m > n) init(2 * m);
//         return _fac[m];
//     }
//     Z invfac(int m) {
//         if (m > n) init(2 * m);
//         return _invfac[m];
//     }
//     Z inv(int m) {
//         if (m > n) init(2 * m);
//         return _inv[m];
//     }
//     Z binom(int n, int m) {
//         if (n < m || m < 0) return 0;
//         return fac(n) * invfac(m) * invfac(n - m);
//     }
// } comb;
// typedef long long LL;
// #define int long long
// typedef unsigned long long ULL;
// typedef pair<LL, LL>PII;
// typedef pair<double, double>PDD;
// typedef pair<char, char>PCC;
// LL n, m, k;
             
// const LL inf = 1e18;
// const LL N = 5e5 + 10;  
// const LL mod = 1e9 + 7;


// signed main() {

    
//     std::ios::sync_with_stdio(false);
//     std::cin.tie(nullptr);

//     int t = 1;
//     //cin >> t;

//     while (t--) {
//         solve();
//     }

//     return 0;
// }

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define int long long
using i64 = long long;
struct Point {
    i64 x;
    i64 y;
    Point(i64 x = 0, i64 y = 0) : x(x), y(y) {}
};

bool operator==(const Point &a, const Point &b) {
    return a.x == b.x && a.y == b.y;
}

Point operator+(const Point &a, const Point &b) {
    return Point(a.x + b.x, a.y + b.y);
}

Point operator-(const Point &a, const Point &b) {
    return Point(a.x - b.x, a.y - b.y);
}
ld len(const Point &a) {
    return sqrtl(a.x * a.x + a.y * a.y);
}
//cos
i64 dot(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
}
//sin
i64 cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}
bool cmp1(Point a,Point b)
{
    if(atan2(a.y,a.x)!=atan2(b.y,b.x))
        return atan2(a.y,a.x)<atan2(b.y,b.x);
    else return a.x<b.x;
}
inline bool cmp(Point A, Point B) { return (A.x == B.x) ? (A.y < B.y) : (A.x < B.x); }

Point O = {0, 0}, P = {-1, 0};
ll operator ^ (Point A, Point B) { return A.x * B.y - B.x * A.y; }
inline bool cmp_vec(Point A, Point B) {
    if (((P - O) ^ (A - O)) == 0 && (P.x - O.x) * (A.x - O.x) > 0) return 1;
    if (((P - O) ^ (B - O)) == 0 && (P.x - O.x) * (B.x - O.x) > 0) return 0;
    if ((((P - O) ^ (A - O)) > 0) != (((P - O) ^ (B - O)) > 0)) return ((P - O) ^ (A - O)) > ((P - O) ^ (B - O));
    return ((A - O) ^ (B - O)) > 0;
}

void g(ld &a) {
    a = max(a, ld(-0.999999999999999));
    a = min(a, ld(0.999999999999999));
}
const ld PI = 3.1415926536;
ld get(Point a, Point b) {
    int dt = dot(a, b);
    int cro = cross(a, b);
    ld le = len(a) * len(b);
    ld ddt = 1.0 * dt / le;
    ld dcro = 1.0 * cro / le;
    g(ddt);
    g(dcro);
    if(cro > 0) {
        return acos(ddt);
    } else if(cro < 0) {
        return 2.0 * PI - acos(ddt);
    } else {
        if(dt > 0) return 0;
        return PI;
    }
    return 0;
}
void solve() {
    int n, k;
    cin >> n >> k;
    vector<Point> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    sort(a.begin(), a.end(), cmp1);
    vector<Point> b(2 * n);
    for(int i = 0; i < n; i++) {
        b[i] = b[i + n] = a[i];
    }
    ld ans = 0;
    for(int i = 0; i < n; i++) {
        int j = i + k;
        if(j == i + n) ans = max(ans, 2.0 * PI);
        else ans = max(ans, get(b[i], b[j]));
    }
    cout << ans << "\n";
}           
    
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(9);
    int T = 1;
    cin >> T;
    while(T--) solve();

    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 4212kb

input:

5
1 1
0 1
8 2
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
4 2
-1 1
0 1
0 2
1 1
4 2
-1000000000 0
-998244353 1
998244353 1
1000000000 0
3 1
0 1
0 2
0 -1

output:

6.283185307
1.570796327
5.497787144
3.141592698
3.141592654

result:

ok 5 numbers

Test #2:

score: -100

Wrong Answer

time: 97ms

memory: 4248kb

input:

10000
16 1
-10 -6
-5 -6
-4 9
-2 5
-2 10
1 -7
1 -5
1 6
3 1
4 -9
6 -10
6 -3
6 1
8 -5
8 -4
9 -4
17 4
-9 2
-8 -4
-8 -3
-8 -1
-6 -2
-6 -1
-6 8
-5 -8
-5 10
-4 8
-2 -8
4 -9
4 0
5 -3
8 -5
9 -2
10 10
10 6
-7 2
-4 6
-2 -7
-2 -1
-1 7
1 -9
1 8
3 -4
7 -4
9 -2
14 3
-9 10
-8 -10
-8 -8
-6 -7
-6 -5
-1 -7
-1 -2
0 -1
...

output:

1.692991497
2.574863436
4.652758267
2.772633107
5.742765807
4.857698991
3.419892313
2.812799962
6.283185307
6.283185307
5.117280767
6.146782703
3.842089024
2.342496717
3.463343208
6.283185307
5.961434753
3.324703471
5.262774928
5.672459343
1.673877935
1.114190855
2.408777552
6.283185307
5.355890089
...

result:

wrong answer 42nd numbers differ - expected: '6.2831853', found: '6.2599337', error = '0.0037006'