QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#641970#1761. Knocked InkwlzAC ✓48ms4392kbC++204.3kb2024-10-15 05:31:142024-10-15 05:31:15

Judging History

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

  • [2024-10-15 05:31:15]
  • 评测
  • 测评结果:AC
  • 用时:48ms
  • 内存:4392kb
  • [2024-10-15 05:31:14]
  • 提交

answer

/**
 * Author: 
 * Date: 2024-08-21
 * Description: Template C++ code
 */
#include <bits/stdc++.h> /** keep-include */
using namespace std;

#define rep(i, a, b) for (auto i = a; i < (b); ++i)
#define repr(i, a, b) for (auto i = (a) - 1; i >= (b); --i)
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<pii>;

template<class T> inline bool cmax(T &a, const T &b)
{ return a < b ? a = b, 1 : 0; }
template<class T> inline bool cmin(T &a, const T &b)
{ return b < a ? a = b, 1 : 0; }

const int inf = 0x3f3f3f3f;
const ll linf = 1e18;
const double dinf = numeric_limits<double>::infinity();

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

typedef Point<double> P;
bool circleInter(P a,P b,double r1,double r2,pair<P, P>* out) {
	if (a == b) { assert(r1 != r2); return false; }
	P vec = b - a;
	double d2 = vec.dist2(), sum = r1+r2, dif = r1-r2,
	       p = (d2 + r1*r1 - r2*r2)/(d2*2), h2 = r1*r1 - p*p*d2;
	if (sum*sum < d2 || dif*dif > d2) return false;
	P mid = a + vec*p, per = vec.perp() * sqrt(fmax(0, h2) / d2);
	*out = {mid + per, mid - per};
	return true;
}

double circleUnion(vector<P>& c, vector<double>& r) {
	double pi = acos(-1), a = 0;
	int n = sz(c);
	vi skip(n, 0);
	rep(i, 0, n) rep(j, 0, n)
		if (!skip[j] && j != i && sgn((c[j] - c[i]).dist() + r[i] - r[j]) <= 0) skip[i] = 1;
	rep(i, 0, n) if (!skip[i]) {
		vector<pair<double, double>> v;
		pair<P, P> p;
		int b = 0, m = 1;
		rep(j, 0, n) if (i != j && !skip[j] && circleInter(c[i], c[j], r[i], r[j], &p) && (p.first - p.second).dist() > 1e-8) {
			b = 1;
			double rs = (p.second - c[i]).angle(), rt = (p.first - c[i]).angle();
			if (rs < 0) rs += 2 * pi;
			if (rt < 0) rt += 2 * pi;
			if (rs < rt) v.pb({rs, rt});
			else v.pb({rs, 2 * pi}), v.pb({0, rt});
		}
		if (!b) { a += pi * r[i] * r[i]; continue; }
		sort(all(v));
		rep(j, 1, sz(v)) if (v[m - 1].second >= v[j].first) v[m - 1].second = max(v[m - 1].second, v[j].second); else v[m++] = v[j];
		v.pb({0, 0}), v[m] = v[0];
		rep(j, 0, m) {
			p.first = P(r[i], 0).rotate(v[j].second) + c[i];
			p.second = P(r[i], 0).rotate(v[j + 1].first) + c[i];
			a += p.first.cross(p.second) / 2;
			double ang = v[j + 1].first - v[j].second;
			if (ang < 0) ang += 2 * pi;
			a += 0.5 * r[i] * r[i] * (ang - sin(ang));
		}
	}
	return a;
}


int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

    int n; double a;
    cin >> n >> a;

    vector<P> p(n);
    vector<double> t(n);
    rep(i, 0, n) {
        cin >> p[i].x >> p[i].y >> t[i];
    }

    double lo = 0, hi = 2e6;
    while (hi - lo > 1e-8) {
        double mid = (lo + hi) / 2;

        vector<double> r(n);
        rep(i, 0, n) {
            r[i] = max(0.0, mid - t[i]);
        }
        if (circleUnion(p, r) >= a) {
            hi = mid;
        } else {
            lo = mid;
        }
    }

    cout << fixed << setprecision(15) << lo << '\n';

	return 0;
}

詳細信息

Test #1:

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

input:

2 1000000000
100 100 1000
99 101 999

output:

18840.172853685999144

result:

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

Test #2:

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

input:

40 1000000
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
0 10 0
1 10 0
2 10 0
3 10 0
4 10 0
5 10 0
6 10 0
7 10 0
8 10 0
9 10 0
10 10 0
10 9 0
10 8 0
10 7 0
10 6 0
10 5 0
10 4 0
10 3 0
10 2 0
10 1 0
10 0 0
9 0 0
8 0 0
7 0 0
6 0 0
5 0 0
4 0 0
3 0 0
2 0 0
1 0 0

output:

557.831094553762341

result:

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

Test #3:

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

input:

100 31415.92
49.901 3.140 0.50
49.606 6.267 1.00
49.114 9.369 1.50
48.429 12.434 2.00
47.553 15.451 2.50
46.489 18.406 3.00
45.241 21.289 3.50
43.815 24.088 4.00
42.216 26.791 4.50
40.451 29.389 5.00
38.526 31.871 5.50
36.448 34.227 6.00
34.227 36.448 6.50
31.871 38.526 7.00
29.389 40.451 7.50
26.79...

output:

69.255115704436321

result:

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

Test #4:

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

input:

100 31415.92
49.901 3.140 5.00
49.606 6.267 5.00
49.114 9.369 5.00
48.429 12.434 5.00
47.553 15.451 5.00
46.489 18.406 5.00
45.241 21.289 5.00
43.815 24.088 5.00
42.216 26.791 5.00
40.451 29.389 5.00
38.526 31.871 5.00
36.448 34.227 5.00
34.227 36.448 5.00
31.871 38.526 5.00
29.389 40.451 5.00
26.79...

output:

55.016567074517297

result:

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

Test #5:

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

input:

9 392392810.12133
301.30821 -754.32553 5.68204
117.95400 -100.82284 85.15355
-696.06419 -651.09441 85.82720
-200.01071 844.85432 18.09701
-285.22194 5.72724 69.10249
872.52912 562.37684 62.95800
495.50699 -277.74212 29.76828
932.05396 -711.34600 87.05425
191.10267 181.65124 3.83350

output:

10354.150355958325235

result:

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

Test #6:

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

input:

22 39650911.44765
-56.78988 376.24577 60.52457
-849.67514 198.07661 19.24914
-804.48122 609.43776 30.08112
639.19475 837.21058 75.93794
-909.69013 -905.68915 25.19425
-944.61178 125.32327 80.08937
517.30567 -26.99543 76.33547
446.51704 487.84666 63.69829
-443.99669 758.01601 20.91661
55.76873 -329.0...

output:

2603.637867288455254

result:

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

Test #7:

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

input:

7 378464144.43626
-564.38640 738.34553 47.01396
251.31029 -129.59945 49.14001
463.87431 97.59501 6.66207
-582.92485 72.10573 80.91733
-812.66456 -983.97154 21.87963
-657.85617 807.04935 27.31978
-82.69392 677.14507 93.20723

output:

10238.447086585721991

result:

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

Test #8:

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

input:

30 178723241.79535
-740.51487 -157.43639 48.41003
4.11977 448.46166 89.67648
541.37089 -507.21839 85.06798
179.39593 -529.22911 65.92012
-922.91852 -120.31960 33.42578
-451.76128 209.54308 7.79540
-287.08584 344.37893 3.95973
839.61175 -885.03516 94.70848
-244.20076 -272.67650 89.21574
877.76301 768...

output:

6551.556580937756735

result:

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

Test #9:

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

input:

28 651760878.39050
825.49683 -740.73884 5.88801
-541.64350 -626.37624 6.43801
-786.45246 313.76982 10.24965
182.74737 -693.75667 71.14469
-525.36681 -165.23371 6.72264
-532.92922 -771.78210 53.72223
162.46485 -636.87421 7.79758
425.48124 330.86437 92.02422
117.85622 101.73753 10.38235
-423.24793 -71...

output:

13442.042858017088292

result:

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

Test #10:

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

input:

28 924766749.98281
833.67815 575.42251 84.06832
328.27062 -245.63567 61.87573
-634.59154 671.16739 10.20498
315.84735 636.66663 58.21541
289.89266 563.81108 70.64238
-798.73052 580.24824 12.99166
-718.40553 475.04058 37.09928
723.79140 -468.90227 92.40819
510.79818 347.63992 41.19336
368.42466 -559....

output:

16295.225527500178941

result:

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

Test #11:

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

input:

22 139337556.27989
713.35746 -26.60308 0.48545
383.07165 -884.54518 93.55719
185.62557 -504.72400 1.53195
967.02748 35.30213 19.62771
72.45571 171.31966 16.08171
806.56423 -782.16123 95.89040
385.78904 635.67906 39.77807
412.12521 507.38177 20.35305
-590.82518 -61.37655 85.63644
-138.80197 -31.73968...

output:

5840.089517768376027

result:

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

Test #12:

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

input:

28 111822992.31097
-504.06108 -646.13799 74.57935
-149.66443 -55.65051 38.28440
-9.72746 -10.85030 18.35269
-189.85575 377.54863 15.74780
310.60478 -494.38497 38.10539
850.31767 -387.11982 23.51145
-771.25559 -74.78903 12.11191
-914.13464 840.27300 6.61844
-83.07294 414.04432 42.43053
-19.74653 -370...

output:

4968.490107600587180

result:

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

Test #13:

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

input:

14 694713017.62670
-240.99079 -251.20076 52.58358
189.88284 -564.83080 52.08813
-69.20493 913.82495 19.66586
729.68816 -611.83454 59.92294
876.58183 -303.23073 4.87457
684.28694 350.87634 43.48789
351.73918 -109.85488 24.55859
526.50948 38.97195 60.56277
552.41063 -294.63470 2.86036
24.24869 -707.40...

output:

14178.926939145243523

result:

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

Test #14:

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

input:

10 748640914.20586
792.15528 -741.34423 19.97922
833.86960 -788.77848 29.17279
969.17253 -280.78457 7.08354
-892.15092 -36.87705 59.43667
790.19003 -651.55029 27.25878
284.06026 -14.89042 51.05338
414.46541 -887.90615 35.81649
810.39411 -245.96515 31.79006
891.39526 -467.68729 36.08814
306.15016 -52...

output:

14777.673802129243995

result:

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

Test #15:

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

input:

11 334028710.89442
3358.81696 5972.03761 5778.39177
5779.60985 -7084.06821 7657.34391
6963.75672 9133.05141 9212.67876
8242.37512 5181.40543 5291.44939
-9899.68032 5280.90038 8212.10001
6403.09358 2694.88597 6542.82229
4839.88645 -2055.71402 471.72711
2833.25201 1591.98352 1553.84494
4434.07408 2511...

output:

8569.761601727066591

result:

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

Test #16:

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

input:

8 486958919.49569
-6378.00230 4124.79507 1242.17757
-6843.47807 -2983.41940 380.28612
2695.42890 1039.31293 531.91499
9180.45506 422.19277 8022.54152
6591.22374 -7176.80244 7424.69196
-2993.90895 292.41045 4828.00270
3007.75318 899.46432 881.96199
6948.59925 -7789.55785 3449.24891

output:

8518.459466813510517

result:

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

Test #17:

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

input:

23 323253532.78062
-7380.30390 8848.96033 7822.36650
-6474.22538 -1401.43605 4825.34450
9303.51157 6409.11032 6301.35695
-1769.82560 2335.85598 6243.16297
-3848.94641 -4267.58843 8625.16360
-7440.42268 -9485.09549 8683.39335
-1443.75402 5319.55953 5010.13408
9401.96060 -907.37882 2884.12483
3001.341...

output:

6810.201363236956240

result:

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

Test #18:

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

input:

25 869950677.41910
6630.32050 -2939.44893 6261.60717
-5577.25373 7539.35538 1018.11709
8816.18403 6856.95081 5298.44129
1894.67949 9242.32126 2101.71277
-7264.42964 -1481.36767 9273.11640
-9582.21161 9663.00725 4494.15670
3673.02734 -2280.19450 133.44490
4249.80751 -4648.67327 946.00031
-808.75522 1...

output:

10226.306505884964281

result:

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

Test #19:

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

input:

16 121450754.42333
-6290.56721 8449.04933 4806.35555
4142.86415 -4982.14081 4119.23804
-4470.93627 1713.41488 5684.39179
-1344.62040 -895.82210 5417.43493
-1316.03977 8301.95790 9128.45699
-1025.26098 -5604.44831 6613.95463
-809.06007 6320.92458 8984.61486
-4459.44103 981.19809 4289.74574
3064.08889...

output:

7248.737915581670677

result:

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

Test #20:

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

input:

23 383225593.03719
7087.90827 -1487.98446 4220.01292
524.51938 -4892.61169 9663.03530
-4918.06541 -1623.06653 6625.82729
-6251.06698 9241.60757 5181.83540
-9272.03902 -8063.88817 5711.64109
6793.16676 715.00358 6742.26054
-312.31287 -8029.92186 2034.25806
5834.79004 -5892.20326 7702.33792
1062.58727...

output:

6111.311417548393365

result:

ok found '6111.3114175', expected '6111.3114176', error '0.0000000'

Test #21:

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

input:

28 814894213.90827
-962.44268 -4620.69521 2353.71800
-5545.31777 -4204.90170 4699.03443
4922.44610 4879.43738 5739.74658
6099.80158 -5981.19325 4933.81937
5247.14063 -5022.53419 1232.68971
-3337.16419 2016.39414 7035.80571
-2510.96903 -7449.03946 7979.27670
-3348.54103 7514.29013 2522.79413
-1303.29...

output:

10781.279666012720554

result:

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

Test #22:

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

input:

10 645067978.32912
-7793.20825 -8910.07178 365.57126
1661.90581 -9647.29815 3152.81555
792.45991 -9830.53957 2290.98267
-2334.05574 3910.05272 4601.88161
-4256.87739 -620.04225 1718.56521
-7668.71892 1037.60125 9843.94400
9231.52728 7002.96240 4795.66629
6328.55590 5756.29425 9843.80669
-7070.05901 ...

output:

9230.111824408028042

result:

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

Test #23:

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

input:

3 308398679.64240
-95.09354 -291.04436 9686.95269
-4909.96221 105.23608 7720.47232
-4153.44420 -9394.17270 9618.33515

output:

15634.003172763754264

result:

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

Test #24:

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

input:

17 650346850.95657
7660.05403 -1955.51006 9687.54762
3062.60224 -4798.50603 6898.33969
1969.19189 -3697.91145 8053.49319
-1483.17236 4219.03875 976.25379
6440.10579 -7648.33137 3094.46571
1235.78045 1117.74149 4030.67626
6725.52986 -6957.77883 247.08469
3169.08858 -6493.92720 3591.99000
1860.62161 7...

output:

10338.865576898115251

result:

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

Test #25:

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

input:

9 436620522.07122
9103.17346 5408.61263 6289.22943
-1165.34206 4634.23112 7013.60003
561.78758 -9104.91527 1164.39690
-2636.00388 2466.57517 4843.16056
9862.14863 -4448.26016 834.24841
-9282.38590 -1441.45234 3805.83592
-4835.01838 2788.66045 3475.59385
-5086.21145 -9108.27308 6677.40826
3586.91609 ...

output:

8240.507186961564003

result:

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

Test #26:

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

input:

70 205578436.443202959
5483.412970614122731 2575.581616239062170 1268.523155825207395
-2891.697963789106721 2843.234312908047205 760.048680016993113
9479.090341220757013 5663.346922713409587 1334.979047184488812
-9421.025053514544836 -1853.957441217161424 1821.433587728968909
4902.488947859357277 -9...

output:

2003.439431845777108

result:

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

Test #27:

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

input:

19 733896868.707149605
-1615.348305660919923 -7323.678751125881729 394.207747169398837
-3019.600727256847545 8788.290589766439645 584.468831113824246
-8554.287767148578442 3315.022160929037206 994.851205782594661
-8637.254006212639408 -871.258240329020506 1955.323727414830038
-8694.846631949153298 -...

output:

8571.736342354084627

result:

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

Test #28:

score: 0
Accepted
time: 15ms
memory: 4300kb

input:

70 792955738.874879706
-9150.254306987282611 -731.985095859118211 805.389855507343416
-5149.793113979330312 -524.367547313444626 1447.463246844021238
820.694851180177030 7914.633541997405554 1092.593991693109492
5043.723017421537633 9813.750656141805684 1508.987011286424805
-6548.593256384533365 -29...

output:

6181.740326596241175

result:

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

Test #29:

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

input:

5 484967069.306765996
-1247.122381924440755 1010.699038323143706 617.317304481604642
6897.136673785809922 -1710.573550697314761 488.479915964966849
-6830.568156672177553 -3967.237688914083515 845.491314875129600
-3022.640403171669392 9128.410812130919448 1498.252422162404100
-4733.764547222713067 -7...

output:

7964.040452790754898

result:

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

Test #30:

score: 0
Accepted
time: 9ms
memory: 4328kb

input:

44 926283681.060938164
5212.047987008760160 1552.660664500801058 1054.977947344736826
-1518.575129206795089 -1787.680878139033252 1164.386721418601667
8725.204500808124172 1714.727819104259613 95.027509649386182
5903.679969101653774 3742.759943446470940 812.170536495965295
-9743.941467062065636 41.2...

output:

7601.307807185265119

result:

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