QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#24149 | #2948. Downsizing | George_Plover | AC ✓ | 3ms | 4316kb | C++20 | 2.0kb | 2022-03-26 17:50:36 | 2022-04-30 05:08:39 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
typedef long long ll;
struct point {
double x, y;
point() {}
point(double _x, double _y) : x(_x), y(_y) {}
point operator-(const point &rhs) const {
return point(x - rhs.x, y - rhs.y);
}
double operator*(const point &rhs) const { return x * rhs.x + y * rhs.y; }
double norm() { return x * x + y * y; }
void read() { scanf("%lf%lf", &x, &y); }
void print() { printf("(%lf,%lf) ", x, y); }
};
double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
double cosa(double la, double lb, double lc) {
return (lb * lb + lc * lc - la * la) / (2 * lb * lc);
}
double get(point a, point b, int r) {
if (cross(a, b) == 0) return 0;
// a.print();
// b.print();
// printf("\n");
point c = b - a;
double la = pow(a.norm(), 0.5), lb = pow(b.norm(), 0.5),
lc = pow(c.norm(), 0.5);
double ca = cosa(la, lb, lc), cb = cosa(lb, lc, la), cc = cosa(lc, la, lb);
double sa = pow(1 - ca * ca, 0.5), sb = pow(1 - cb * cb, 0.5);
double s2a = 2 * sa * ca, s2b = 2 * sb * cb;
double C = acos(cc);
// printf("%lf %lf %lf \n", la, lb, lc);
// printf("%lf %lf %lf \n", ca, cb, cc);
// printf("%lf %lf\n", sa, sb);
// printf("%lf %lf\n", s2a, s2b);
double ret = r * r / (8 * b.norm() * sa * sa) * r * r * (C * 2 + s2a + s2b);
// printf("%lf\n", ret);
if (cross(a, b) < 0) ret = -ret;
return ret;
}
const int N = 105;
int n;
point a[N];
int main() {
point base;
base.read();
double r;
scanf("%lf", &r);
scanf("%d", &n);
rep(i, 0, n - 1) {
a[i].read();
a[i] = a[i] - base;
}
a[n] = a[0];
double ans = 0;
rep(i, 0, n - 1) {
double tmp = get(a[i], a[i + 1], r);
ans -= tmp;
// printf("%.8lf\n", tmp);
}
printf("%.8lf\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3936kb
input:
0 0 10 4 -10 -10 -10 -20 10 -20 10 -10
output:
42.38678534
result:
ok found '42.3867853', expected '42.3867853', error '0.0000000'
Test #2:
score: 0
Accepted
time: 3ms
memory: 3996kb
input:
0 0 4 4 0 10 -3 7 0 4 3 7
output:
2.56174561
result:
ok found '2.5617456', expected '2.5617456', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4136kb
input:
0 0 10 4 -20 5 -15 0 0 15 -5 20
output:
33.14971023
result:
ok found '33.1497102', expected '33.1497102', error '0.0000000'
Test #4:
score: 0
Accepted
time: 3ms
memory: 4092kb
input:
0 0 10 3 -15 20 -20 -15 -15 0
output:
5.08877513
result:
ok found '5.0887751', expected '5.0887751', error '0.0000000'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3968kb
input:
0 0 10 4 -10 -10 -15 -15 15 -15 10 -10
output:
35.70550454
result:
ok found '35.7055045', expected '35.7055045', error '0.0000000'
Test #6:
score: 0
Accepted
time: 3ms
memory: 4112kb
input:
-100 -100 75 5 -225 -225 -225 -275 -125 -275 -125 -225 -175 -175
output:
498.86030113
result:
ok found '498.8603011', expected '498.8603010', error '0.0000000'
Test #7:
score: 0
Accepted
time: 3ms
memory: 3948kb
input:
1090 -50 30 6 1090 10 1090 40 1060 70 970 -20 1000 -50 1030 -50
output:
235.26161844
result:
ok found '235.2616184', expected '235.2616180', error '0.0000000'
Test #8:
score: 0
Accepted
time: 3ms
memory: 3952kb
input:
-200 63 96 7 0 0 0 -47 101 -141 202 -141 303 -94 303 -47 101 0
output:
216.64365164
result:
ok found '216.6436516', expected '216.6436516', error '0.0000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 4060kb
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.51008316
result:
ok found '197884.5100832', expected '197884.5100830', error '0.0000000'
Test #10:
score: 0
Accepted
time: 3ms
memory: 3952kb
input:
3820 740 5160 5 -6400 -5540 2560 8360 -5020 8880 -8680 2220 -7520 -4520
output:
12675159.35426053
result:
ok found '12675159.3542605', expected '12675159.3542605', error '0.0000000'
Test #11:
score: 0
Accepted
time: 3ms
memory: 4316kb
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.49473595
result:
ok found '3537619.4947360', expected '3537619.4949730', error '0.0000000'
Test #12:
score: 0
Accepted
time: 3ms
memory: 3952kb
input:
40 20 5420 5 -140 9080 6460 600 9220 -340 9740 9920 880 9840
output:
12509089.02823808
result:
ok found '12509089.0282381', expected '12509089.0282381', error '0.0000000'
Test #13:
score: 0
Accepted
time: 3ms
memory: 4044kb
input:
-4220 300 100 4 -3600 9900 -3660 -9740 9620 -9740 9660 9780
output:
224.12827994
result:
ok found '224.1282799', expected '224.1282800', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 4020kb
input:
-7840 -7740 1900 4 -9900 9200 8760 -9800 9780 -8920 -8940 9900
output:
16882.86790729
result:
ok found '16882.8679073', expected '16882.8679070', error '0.0000000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 4088kb
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.43067329
result:
ok found '5646.4306733', expected '5646.4306730', error '0.0000000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 4236kb
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.01766440
result:
ok found '0.0176644', expected '0.0176644', error '0.0000000'
Test #17:
score: 0
Accepted
time: 3ms
memory: 4060kb
input:
0 -9950 50 3 -10000 0 10000 0 0 10000
output:
0.02038846
result:
ok found '0.0203885', expected '0.0203885', error '0.0000000'
Test #18:
score: 0
Accepted
time: 3ms
memory: 3996kb
input:
-9900 9900 100 3 -10000 9800 -5000 -10000 10000 9800
output:
6135.53298977
result:
ok found '6135.5329898', expected '6135.5329900', error '0.0000000'
Test #19:
score: 0
Accepted
time: 3ms
memory: 3948kb
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.88835948
result:
ok found '149865.8883595', expected '149865.8883600', error '0.0000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
0 0 5000 4 9000 -10000 10000 -10000 10000 -9000 -9000 -9000
output:
514362.44238832
result:
ok found '514362.4423883', expected '514362.4423880', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 4176kb
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.06181660
result:
ok found '0.0618166', expected '0.0618160', error '0.0000006'
Test #22:
score: 0
Accepted
time: 3ms
memory: 4096kb
input:
-3000 3100 1740 8 820 -2640 3680 -1880 4000 720 2680 9000 1540 9160 740 8920 -60 8080 -260 6720
output:
494634.33559063
result:
ok found '494634.3355906', expected '494634.3355910', error '0.0000000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 4044kb
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.82545917
result:
ok found '91873.8254592', expected '91873.8254590', error '0.0000000'
Test #24:
score: 0
Accepted
time: 3ms
memory: 4056kb
input:
-1180 -400 10 4 9991 9991 9990 9991 9990 9990 9991 9990
output:
0.00000000
result:
ok found '0.0000000', expected '0.0000000', error '0.0000000'