QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#772936#1793. Beer CoastersI_be_wannaAC ✓1ms4456kbC++173.5kb2024-11-22 23:02:482024-11-22 23:02:49

Judging History

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

  • [2024-11-22 23:02:49]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4456kb
  • [2024-11-22 23:02:48]
  • 提交

answer

#include <bits/stdc++.h>
#define inf 1000000000000
#define M 100009
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
struct Point
{
    double x, y;
    Point() {}
    Point(double xx, double yy)
    {
        x = xx;
        y = yy;
    }
    Point operator-(Point s) { return Point(x - s.x, y - s.y); }
    Point operator+(Point s) { return Point(x + s.x, y + s.y); }
    double operator*(Point s) { return x * s.x + y * s.y; }
    double operator^(Point s) { return x * s.y - y * s.x; }
} p[M];
double max(double a, double b) { return a > b ? a : b; }
double min(double a, double b) { return a < b ? a : b; }
double len(Point a) { return sqrt(a * a); }
double dis(Point a, Point b) { return len(b - a); } //Á½µãÖ®¼äµÄ¾àÀë
double cross(Point a, Point b, Point c)             //²æ³Ë
{
    return (b - a) ^ (c - a);
}
double dot(Point a, Point b, Point c) //µã³Ë
{
    return (b - a) * (c - a);
}
int judge(Point a, Point b, Point c) //ÅжÏcÊÇ·ñÔÚabÏ߶ÎÉÏ£¨Ç°ÌáÊÇcÔÚÖ±ÏßabÉÏ£©
{
    if (c.x >= min(a.x, b.x) && c.x <= max(a.x, b.x) && c.y >= min(a.y, b.y) && c.y <= max(a.y, b.y))
        return 1;
    return 0;
}
double area(Point b, Point c, double r)
{
    Point a(0.0, 0.0);
    if (dis(b, c) < eps)
        return 0.0;
    double h = fabs(cross(a, b, c)) / dis(b, c);
    if (dis(a, b) > r - eps && dis(a, c) > r - eps) //Á½¸ö¶Ëµã¶¼ÔÚÔ²µÄÍâÃæÔò·ÖΪÁ½ÖÖÇé¿ö
    {
        double angle = acos(dot(a, b, c) / dis(a, b) / dis(a, c));
        if (h > r - eps)
            return 0.5 * r * r * angle;
        else if (dot(b, a, c) > 0 && dot(c, a, b) > 0)
        {
            double angle1 = 2 * acos(h / r);
            return 0.5 * r * r * fabs(angle - angle1) + 0.5 * r * r * sin(angle1);
        }
        else
            return 0.5 * r * r * angle;
    }
    else if (dis(a, b) < r + eps && dis(a, c) < r + eps)
        return 0.5 * fabs(cross(a, b, c)); //Á½¸ö¶Ëµã¶¼ÔÚÔ²ÄÚµÄÇé¿ö
    else                                   //Ò»¸ö¶ËµãÔÚÔ²ÉÏÒ»¸ö¶ËµãÔÚÔ²ÄÚµÄÇé¿ö
    {
        if (dis(a, b) > dis(a, c))
            swap(b, c); //ĬÈÏbÔÚÔ²ÄÚ
        if (fabs(dis(a, b)) < eps)
            return 0.0; //ab¾àÀëΪ0Ö±½Ó·µ»Ø0
        if (dot(b, a, c) < eps)
        {
            double angle1 = acos(h / dis(a, b));
            double angle2 = acos(h / r) - angle1;
            double angle3 = acos(h / dis(a, c)) - acos(h / r);
            return 0.5 * dis(a, b) * r * sin(angle2) + 0.5 * r * r * angle3;
        }
        else
        {
            double angle1 = acos(h / dis(a, b));
            double angle2 = acos(h / r);
            double angle3 = acos(h / dis(a, c)) - angle2;
            return 0.5 * r * dis(a, b) * sin(angle1 + angle2) + 0.5 * r * r * angle3;
        }
    }
}
int main()
{
    int n = 4;
    double rx, ry, R;
    scanf("%lf%lf%lf", &rx, &ry, &R);
    scanf("%lf%lf%lf%lf", &p[1].x, &p[1].y, &p[3].x, &p[3].y);
    p[2].x = p[1].x;
    p[2].y = p[3].y;
    p[4].x = p[3].x;
    p[4].y = p[1].y;
    p[5] = p[1];
    Point O(rx, ry);
    for (int i = 1; i <= n + 1; i++)
        p[i] = p[i] - O;
    O = Point(0, 0);
    double sum = 0;
    for (int i = 1; i <= n; i++)
    {
        int j = i + 1;
        double s = area(p[i], p[j], R);
        if (cross(O, p[i], p[j]) > 0)
            sum += s;
        else
            sum -= s;
    }
    printf("%.4lf\n", fabs(sum));
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

0 0 1 0 -2 2 2

output:

1.5708

result:

ok found '1.57080', expected '1.57080', error '0.00000'

Test #2:

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

input:

0 0 1 -2 -2 2 2


output:

3.1416

result:

ok found '3.14160', expected '3.14159', error '0.00000'

Test #3:

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

input:

-1 0 4 1 -1 -1 1

output:

4.0000

result:

ok found '4.00000', expected '4.00000', error '0.00000'

Test #4:

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

input:

0 0 4 3 3 -3 -3

output:

35.7595

result:

ok found '35.75950', expected '35.75951', error '0.00000'

Test #5:

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

input:

1 1 4 4 4 -3 -3

output:

43.0125

result:

ok found '43.01250', expected '43.01249', error '0.00000'

Test #6:

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

input:

-1 -1 4 2 2 1 1

output:

0.9399

result:

ok found '0.93990', expected '0.93988', error '0.00002'

Test #7:

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

input:

1 1 3 -4 1 5 -1

output:

11.0397

result:

ok found '11.03970', expected '11.03968', error '0.00000'

Test #8:

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

input:

0 2 2 -1 0 1 -2

output:

0.0000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #9:

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

input:

0 0 5 3 3 4 4

output:

0.5474

result:

ok found '0.54740', expected '0.54743', error '0.00003'

Test #10:

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

input:

959 -557 912 -664 -599 447 -342

output:

100954.7830

result:

ok found '100954.78300', expected '100954.78304', error '0.00000'

Test #11:

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

input:

498 -750 442 553 -561 634 -277

output:

19593.4217

result:

ok found '19593.42170', expected '19593.42174', error '0.00000'

Test #12:

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

input:

-707 -918 242 -332 789 -18 975

output:

0.0000

result:

ok found '0.00000', expected '0.00000', error '0.00000'

Test #13:

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

input:

-937 -462 705 -910 -498 591 871

output:

395729.1423

result:

ok found '395729.14230', expected '395729.14227', error '0.00000'

Test #14:

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

input:

-220 -315 849 -616 57 953 120

output:

71990.1170

result:

ok found '71990.11700', expected '71990.11702', error '0.00000'

Test #15:

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

input:

170 -93 698 -514 395 -305 469

output:

286.5961

result:

ok found '286.59610', expected '286.59608', error '0.00000'

Test #16:

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

input:

-947 -673 996 -957 48 948 759

output:

132674.9719

result:

ok found '132674.97190', expected '132674.97185', error '0.00000'

Test #17:

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

input:

851 -201 414 -697 -366 587 609

output:

56155.7494

result:

ok found '56155.74940', expected '56155.74936', error '0.00000'

Test #18:

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

input:

-584 -18 336 -803 -717 197 -264

output:

28251.4505

result:

ok found '28251.45050', expected '28251.45046', error '0.00000'

Test #19:

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

input:

-943 313 872 -723 351 226 722

output:

228356.0806

result:

ok found '228356.08060', expected '228356.08056', error '0.00000'

Test #20:

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

input:

-311 -127 621 -912 352 -101 875

output:

65653.1909

result:

ok found '65653.19090', expected '65653.19088', error '0.00000'

Test #21:

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

input:

333 790 238 247 -198 372 819

output:

32878.7153

result:

ok found '32878.71530', expected '32878.71533', error '0.00000'

Test #22:

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

input:

-299 554 352 -773 117 -465 424

output:

18009.1782

result:

ok found '18009.17820', expected '18009.17817', error '0.00000'

Test #23:

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

input:

-268 708 280 -423 -211 8 792

output:

138573.9591

result:

ok found '138573.95910', expected '138573.95912', error '0.00000'

Test #24:

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

input:

-589 142 253 -986 100 -413 486

output:

108857.4628

result:

ok found '108857.46280', expected '108857.46278', error '0.00000'

Test #25:

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

input:

898 -73 713 274 -537 447 581

output:

155642.6540

result:

ok found '155642.65400', expected '155642.65402', error '0.00000'

Test #26:

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

input:

342 992 576 91 -33 396 929

output:

151703.6992

result:

ok found '151703.69920', expected '151703.69921', error '0.00000'

Test #27:

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

input:

457 -582 329 -238 -965 -119 -97

output:

0.0000

result:

ok found '0.00000', expected '0.00000', error '0.00000'

Test #28:

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

input:

680 642 895 -574 297 191 855

output:

216905.7857

result:

ok found '216905.78570', expected '216905.78567', error '0.00000'

Test #29:

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

input:

410 834 490 -762 513 474 885

output:

193926.1190

result:

ok found '193926.11900', expected '193926.11901', error '0.00000'

Test #30:

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

input:

309 -31 389 -620 -930 429 -182

output:

89427.3387

result:

ok found '89427.33870', expected '89427.33866', error '0.00000'

Test #31:

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

input:

470 510 519 -403 460 154 503

output:

8688.9128

result:

ok found '8688.91280', expected '8688.91278', error '0.00000'

Test #32:

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

input:

807 152 462 348 -703 620 202

output:

97160.0115

result:

ok found '97160.01150', expected '97160.01151', error '0.00000'

Test #33:

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

input:

500 894 885 -619 214 298 388

output:

78545.5944

result:

ok found '78545.59440', expected '78545.59439', error '0.00000'

Test #34:

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

input:

-620 -4 655 -15 -195 568 -94

output:

3439.6990

result:

ok found '3439.69900', expected '3439.69901', error '0.00000'

Test #35:

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

input:

-705 862 553 -623 498 743 738

output:

97951.3622

result:

ok found '97951.36220', expected '97951.36217', error '0.00000'

Test #36:

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

input:

-710 446 830 -498 -440 -261 546

output:

203270.3932

result:

ok found '203270.39320', expected '203270.39325', error '0.00000'

Test #37:

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

input:

-442 -511 559 -159 -488 876 -428

output:

16392.5812

result:

ok found '16392.58120', expected '16392.58115', error '0.00000'

Test #38:

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

input:

-535 -880 509 -999 -130 -330 304

output:

0.0000

result:

ok found '0.00000', expected '0.00000', error '0.00000'

Test #39:

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

input:

-839 -211 842 -265 -28 665 489

output:

66301.2753

result:

ok found '66301.27530', expected '66301.27533', error '0.00000'

Test #40:

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

input:

668 -281 575 -151 -613 688 600

output:

457496.5751

result:

ok found '457496.57510', expected '457496.57511', error '0.00000'

Test #41:

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

input:

724 600 746 -995 -357 44 668

output:

18040.2665

result:

ok found '18040.26650', expected '18040.26650', error '0.00000'

Test #42:

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

input:

-591 -248 493 -829 -186 -243 635

output:

232266.8671

result:

ok found '232266.86710', expected '232266.86713', error '0.00000'

Test #43:

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

input:

840 -480 556 -452 -511 608 367

output:

127685.4781

result:

ok found '127685.47810', expected '127685.47805', error '0.00000'

Test #44:

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

input:

-856 -490 263 -853 -518 -352 809

output:

60802.2876

result:

ok found '60802.28760', expected '60802.28765', error '0.00000'

Test #45:

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

input:

507 297 981 -851 -812 945 315

output:

1196319.1177

result:

ok found '1196319.11770', expected '1196319.11768', error '0.00000'

Test #46:

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

input:

711 537 493 -562 62 957 233

output:

89223.2645

result:

ok found '89223.26450', expected '89223.26455', error '0.00000'

Test #47:

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

input:

758 -483 819 -969 -268 943 -181

output:

83666.5005

result:

ok found '83666.50050', expected '83666.50052', error '0.00000'

Test #48:

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

input:

-924 -331 594 -935 -203 -300 -105

output:

56569.5263

result:

ok found '56569.52630', expected '56569.52632', error '0.00000'

Test #49:

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

input:

-326 777 330 -748 -323 -501 564

output:

2842.3203

result:

ok found '2842.32030', expected '2842.32027', error '0.00000'

Test #50:

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

input:

435 -357 792 -624 -367 95 57

output:

176034.3764

result:

ok found '176034.37640', expected '176034.37636', error '0.00000'

Test #51:

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

input:

364 307 808 -130 -858 890 863

output:

1332494.1362

result:

ok found '1332494.13620', expected '1332494.13619', error '0.00000'

Test #52:

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

input:

452 850 942 -215 -546 528 186

output:

149072.9644

result:

ok found '149072.96440', expected '149072.96441', error '0.00000'

Test #53:

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

input:

-917 -451 446 -606 -179 969 973

output:

1060.8662

result:

ok found '1060.86620', expected '1060.86620', error '0.00000'

Test #54:

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

input:

-935 797 981 22 -897 792 717

output:

1626.2671

result:

ok found '1626.26710', expected '1626.26707', error '0.00000'

Test #55:

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

input:

676 129 885 -374 -12 696 933

output:

738134.8941

result:

ok found '738134.89410', expected '738134.89411', error '0.00000'

Test #56:

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

input:

722 -753 851 -549 106 -381 611

output:

0.0000

result:

ok found '0.00000', expected '0.00000', error '0.00000'

Test #57:

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

input:

-335 -43 984 -114 -601 951 844

output:

931319.4875

result:

ok found '931319.48750', expected '931319.48752', error '0.00000'

Test #58:

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

input:

-277 520 7 -493 312 -314 977

output:

0.0000

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #59:

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

input:

501 875 655 -219 -311 -104 356

output:

0.0000

result:

ok found '0.00000', expected '0.00000', error '0.00000'

Test #60:

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

input:

41 -846 691 423 -525 815 -134

output:

34260.8728

result:

ok found '34260.87280', expected '34260.87282', error '0.00000'

Test #61:

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

input:

-450 -6 488 -566 -406 438 794

output:

459825.6044

result:

ok found '459825.60440', expected '459825.60437', error '0.00000'

Test #62:

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

input:

956 41 476 516 378 656 470

output:

608.9948

result:

ok found '608.99480', expected '608.99482', error '0.00000'

Test #63:

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

input:

263 -981 878 -648 -299 370 -214

output:

51088.4100

result:

ok found '51088.41000', expected '51088.41000', error '0.00000'

Test #64:

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

input:

999 719 631 -966 800 391 816

output:

266.7920

result:

ok found '266.79200', expected '266.79203', error '0.00000'

Test #65:

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

input:

345 -599 801 -944 -615 912 -153

output:

612584.5988

result:

ok found '612584.59880', expected '612584.59882', error '0.00000'

Test #66:

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

input:

83 -353 755 -279 -341 -1 422

output:

195818.5489

result:

ok found '195818.54890', expected '195818.54890', error '0.00000'

Test #67:

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

input:

343 -726 833 -692 -59 585 61

output:

77047.3254

result:

ok found '77047.32540', expected '77047.32538', error '0.00000'

Test #68:

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

input:

-191 -425 941 -957 -233 603 546

output:

976015.6491

result:

ok found '976015.64910', expected '976015.64908', error '0.00000'

Test #69:

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

input:

-919 307 778 -338 257 349 605

output:

62728.2465

result:

ok found '62728.24650', expected '62728.24654', error '0.00000'

Test #70:

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

input:

182 607 439 14 -829 155 606

output:

59923.5386

result:

ok found '59923.53860', expected '59923.53856', error '0.00000'

Test #71:

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

input:

-215 -366 795 317 -981 713 476

output:

215154.0328

result:

ok found '215154.03280', expected '215154.03285', error '0.00000'

Test #72:

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

input:

-582 960 815 -844 308 -160 463

output:

106020.0000

result:

ok found '106020.00000', expected '106020.00000', error '0.00000'

Test #73:

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

input:

-989 -581 571 -782 -611 131 174

output:

151429.6664

result:

ok found '151429.66640', expected '151429.66640', error '0.00000'

Test #74:

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

input:

917 -420 639 454 -319 649 493

output:

81621.3627

result:

ok found '81621.36270', expected '81621.36272', error '0.00000'

Test #75:

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

input:

-814 -904 717 -907 -462 433 709

output:

133646.8179

result:

ok found '133646.81790', expected '133646.81792', error '0.00000'

Test #76:

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

input:

664 -942 862 -350 -573 652 988

output:

269592.4711

result:

ok found '269592.47110', expected '269592.47111', error '0.00000'

Test #77:

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

input:

767 106 980 189 -816 332 -112

output:

88598.8327

result:

ok found '88598.83270', expected '88598.83271', error '0.00000'

Test #78:

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

input:

62 74 976 -892 212 -475 926

output:

191261.8688

result:

ok found '191261.86880', expected '191261.86883', error '0.00000'

Test #79:

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

input:

731 642 663 -563 -295 -138 887

output:

0.0000

result:

ok found '0.00000', expected '0.00000', error '0.00000'