QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#714451#2948. DownsizingstavageAC ✓2ms7084kbC++202.8kb2024-11-05 23:18:372024-11-05 23:18:44

Judging History

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

  • [2024-11-05 23:18:44]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:7084kb
  • [2024-11-05 23:18:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
#define int LL
#define double LD
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const double PI = acosl(-1);
const double eps = 1e-8;

struct Point {
  double x, y;
  Point(double x = 0, double y = 0) : x(x), y(y) {}
};
typedef Point Vector;
Point operator+(Point a, Point b) { return Point(a.x + b.x, a.y + b.y); }
Point operator-(Point a, Point b) { return Point(a.x - b.x, a.y - b.y); }
Point operator*(Point a, double p) { return Point(a.x * p, a.y * p); }
Point operator/(Point a, double p) { return Point(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); }
int sgn(double x)
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}
bool operator==(const Point &a, const Point &b) { return !sgn(a.x - b.x) && !sgn(a.y - b.y); }
double dis(Point a, Point b)
{
    return sqrtl((a.x - b.x) * (a.x - b.x) * 1.L + (a.y - b.y) * (a.y - b.y));
}
double Cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
double Dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
double Length(Vector a) { return sqrtl(Dot(a, a)); }

double calc(Vector a, Vector b, double r)
{
    if (Cross(a, b) == 0) return 0;
    auto Yx = [](double a, double b, double c)->double {
      double t = (a * a + b * b - c * c) / (2.L * a * b);
      return t;
    };
//    cout<<Yx(1,2,sqrtl(3))<<endl;
    Vector c = a - b;
//    cout<<c.x<<" "<<c.y<<endl;
    double da = Length(a), db = Length(b), dc = Length(c);
//    cout<<da<<" "<<db<<" "<<dc<<endl;
    double cosa = Yx(db, dc, da), cosb = Yx(da, dc, db), cosc = Yx(da, db, dc);
//    cout<<cosa<<" "<<cosb<<" "<<cosc<<endl;
    double sina = sqrtl(1 - cosa * cosa), sinb = sqrtl(1 - cosb * cosb), sinc = sqrtl(1 - cosc * cosc);
    double sin2a = 2 * sina * cosa, sin2b = 2 * sinb * cosb;
    double C = acos(cosc);
    double res = r * r / (8 * db * db * sina * sina) * r * r * (2 * C + sin2a + sin2b);
    if (Cross(a, b) < 0) res = -res;
    return res;
}
Point a[N];
void solve()
{
    Point p, c;
    double r;
    cin >> p.x >> p.y >> r;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
        a[i] = a[i] - p;
//        cout<<a[i].x<<" "<<a[i].y<<endl;
    }
    double ans = 0;
    for (int i = 0; i < n; i++) {
        double tmp = calc(a[i], a[(i + 1) % n], r);
        ans -= tmp;
//        cout<<tmp<<endl;
    }
//    cout << ans << endl;
    cout << fabs(ans) << endl;
}

signed main()
{
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    int _ = 1;
    while (_--) {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7028kb

input:

0 0 10
4 -10 -10 -10 -20 10 -20 10 -10

output:

42.3867853375

result:

ok found '42.3867853', expected '42.3867853', error '0.0000000'

Test #2:

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

input:

0 0 4
4 0 10 -3 7 0 4 3 7

output:

2.5617456077

result:

ok found '2.5617456', expected '2.5617456', error '0.0000000'

Test #3:

score: 0
Accepted
time: 2ms
memory: 7084kb

input:

0 0 10
4 -20 5 -15 0 0 15 -5 20

output:

33.1497102299

result:

ok found '33.1497102', expected '33.1497102', error '0.0000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 6924kb

input:

0 0 10
3 -15 20 -20 -15 -15 0

output:

5.0887751263

result:

ok found '5.0887751', expected '5.0887751', error '0.0000000'

Test #5:

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

input:

0 0 10
4 -10 -10 -15 -15 15 -15 10 -10

output:

35.7055045388

result:

ok found '35.7055045', expected '35.7055045', error '0.0000000'

Test #6:

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

input:

-100 -100 75
5 -225 -225 -225 -275 -125 -275 -125 -225 -175 -175

output:

498.8603011303

result:

ok found '498.8603011', expected '498.8603010', error '0.0000000'

Test #7:

score: 0
Accepted
time: 2ms
memory: 7036kb

input:

1090 -50 30
6 1090 10 1090 40 1060 70 970 -20 1000 -50 1030 -50

output:

235.2616184420

result:

ok found '235.2616184', expected '235.2616180', error '0.0000000'

Test #8:

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

input:

-200 63 96
7 0 0 0 -47 101 -141 202 -141 303 -94 303 -47 101 0

output:

216.6436516402

result:

ok found '216.6436516', expected '216.6436516', error '0.0000000'

Test #9:

score: 0
Accepted
time: 2ms
memory: 7044kb

input:

7900 5440 1220
10 5820 5180 3780 7200 1560 7920 -140 7860 -1620 7080 -3920 4260 -2680 20 -320 -1040 4180 -120 5620 3080

output:

197884.5100831532

result:

ok found '197884.5100832', expected '197884.5100830', error '0.0000000'

Test #10:

score: 0
Accepted
time: 2ms
memory: 7036kb

input:

3820 740 5160
5 -6400 -5540 2560 8360 -5020 8880 -8680 2220 -7520 -4520

output:

12675159.3542605341

result:

ok found '12675159.3542605', expected '12675159.3542605', error '0.0000000'

Test #11:

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

input:

5920 6200 3440
21 2360 7720 600 8500 -1620 9060 -4420 9120 -5680 8940 -6820 8560 -7460 8120 -8320 6120 -8600 4360 -8640 2960 -8460 1420 -7400 -1520 -6840 -2500 -6320 -3180 -5640 -3580 -4960 -3900 -4360 -4040 -3020 -3980 -1860 -3560 -1280 -2920 -820 -2200

output:

3537619.4949733120

result:

ok found '3537619.4949733', expected '3537619.4949730', error '0.0000000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 7036kb

input:

40 20 5420
5 -140 9080 6460 600 9220 -340 9740 9920 880 9840

output:

12509089.0282381101

result:

ok found '12509089.0282381', expected '12509089.0282381', error '0.0000000'

Test #13:

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

input:

-4220 300 100
4 -3600 9900 -3660 -9740 9620 -9740 9660 9780

output:

224.1282799386

result:

ok found '224.1282799', expected '224.1282800', error '0.0000000'

Test #14:

score: 0
Accepted
time: 2ms
memory: 7028kb

input:

-7840 -7740 1900
4 -9900 9200 8760 -9800 9780 -8920 -8940 9900

output:

16882.8679072916

result:

ok found '16882.8679073', expected '16882.8679070', error '0.0000000'

Test #15:

score: 0
Accepted
time: 2ms
memory: 7016kb

input:

0 0 100
22 100 100 100 -100 200 -200 210 -209 220 -217 230 -224 240 -230 250 -235 260 -239 270 -242 280 -244 290 -245 290 245 280 244 270 242 260 239 250 235 240 230 230 224 220 217 210 209 200 200

output:

5646.4306732866

result:

ok found '5646.4306733', expected '5646.4306730', error '0.0000000'

Test #16:

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

input:

-9999 -9999 1
77 -9996 -9997 -9096 -9497 -8216 -8997 -7356 -8497 -6516 -7997 -5696 -7497 -4896 -6997 -4116 -6497 -3356 -5997 -2616 -5497 -1896 -4997 -1196 -4497 -516 -3997 144 -3497 784 -2997 1404 -2497 2004 -1997 2584 -1497 3144 -997 3684 -497 4204 3 4704 503 5184 1003 5644 1503 6084 2003 6504 2503...

output:

0.0176644010

result:

ok found '0.0176644', expected '0.0176644', error '0.0000000'

Test #17:

score: 0
Accepted
time: 2ms
memory: 7032kb

input:

0 -9950 50
3 -10000 0 10000 0 0 10000

output:

0.0203884645

result:

ok found '0.0203885', expected '0.0203885', error '0.0000000'

Test #18:

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

input:

-9900 9900 100
3 -10000 9800 -5000 -10000 10000 9800

output:

6135.5329897785

result:

ok found '6135.5329898', expected '6135.5329900', error '0.0000000'

Test #19:

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

input:

0 9000 1000
100 7000 0 6986 439 6944 877 6876 1311 6780 1740 6657 2163 6508 2576 6333 2980 6134 3372 5910 3750 5663 4114 5393 4461 5102 4791 4791 5102 4461 5393 4114 5663 3750 5910 3372 6134 2980 6333 2576 6508 2163 6657 1740 6780 1311 6876 877 6944 439 6986 0 7000 -439 6986 -877 6944 -1311 6876 -17...

output:

149865.8883599981

result:

ok found '149865.8883600', expected '149865.8883600', error '0.0000000'

Test #20:

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

input:

0 0 5000
4 9000 -10000 10000 -10000 10000 -9000 -9000 -9000

output:

514362.4423883169

result:

ok found '514362.4423883', expected '514362.4423880', error '0.0000000'

Test #21:

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

input:

9000 9000 100
100 2828 2828 2778 2867 2717 2894 2645 2910 2563 2915 2471 2908 2369 2890 2258 2860 2137 2819 2009 2767 1872 2703 1728 2630 1577 2545 1420 2451 1258 2347 1090 2234 918 2112 742 1982 564 1844 383 1698 201 1546 18 1388 -164 1224 -347 1056 -528 883 -707 707 -883 528 -1056 347 -1224 164 -1...

output:

0.0618165973

result:

ok found '0.0618166', expected '0.0618160', error '0.0000006'

Test #22:

score: 0
Accepted
time: 2ms
memory: 6968kb

input:

-3000 3100 1740
8 820 -2640 3680 -1880 4000 720 2680 9000 1540 9160 740 8920 -60 8080 -260 6720

output:

494634.3355906262

result:

ok found '494634.3355906', expected '494634.3355910', error '0.0000000'

Test #23:

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

input:

-7360 -7740 580
20 -6480 -7920 -6180 -8380 -5520 -8940 -4220 -9320 -3240 -9520 -1040 -9640 4180 -9160 6380 -8540 8160 -7200 9180 -5660 9560 -3480 9740 1000 9440 5500 8720 8000 7640 9460 3560 9800 -5180 8720 -5860 7260 -6480 3960 -6880 60

output:

91873.8254591675

result:

ok found '91873.8254592', expected '91873.8254590', error '0.0000000'

Test #24:

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

input:

-1180 -400 10
4 9991 9991 9990 9991 9990 9990 9991 9990

output:

0.0000000000

result:

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