QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#714451 | #2948. Downsizing | stavage | AC ✓ | 2ms | 7084kb | C++20 | 2.8kb | 2024-11-05 23:18:37 | 2024-11-05 23:18:44 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'