QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191515#7527. Doors of the WardrobeDays_of_Future_Past#AC ✓1566ms28936kbC++144.0kb2023-09-30 00:19:572023-09-30 00:19:58

Judging History

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

  • [2023-09-30 00:19:58]
  • 评测
  • 测评结果:AC
  • 用时:1566ms
  • 内存:28936kb
  • [2023-09-30 00:19:57]
  • 提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
typedef long long LL;
typedef long double D;
const int N = 100011;
mt19937 gene(233);
struct P {
	D x, y;
	void scan() {
		cin >> x >> y;
	}
	bool operator < (const P & b) const {
		return x < b.x;
	}
	P operator - (const P & b) const {
		return P{x - b.x, y - b.y};
	}
	P operator + (const P & b) const {
		return P{x + b.x, y + b.y};
	}
	D operator * (const P & b) const {
		return x * b.y - y * b.x;
	}
	D operator % (const P & b) const {
		return x * b.x + y * b.y;
	}
	D sqrlen() const {
		return x * x + y * y;
	}
	D len() const {
		return sqrt(sqrlen());
	}
	P zoom(const D & l) const {
		D lambda = l / len();
		return P{lambda * x, lambda * y};
	}
	void print() const {
		cout << x << ' ' << y << endl;
	}
	void rand() {
		x = gene();
		y = gene();
	}
} a[N], d[N];
P operator * (const D & x, const P & b) {
	return P{x * b.x, x * b.y};
}
typedef tree<P, null_type, less<P>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ordered_set hull[2];
void insert(P x) {
	for(int d = 0; d < 2; d++) {
		auto itr = hull[d].lower_bound(x);
		bool flag = false;
		if(itr == hull[d].end()) {
			flag = true;
		}else if(itr->x == x.x) {
			//cout << itr->y << '?' << x.y << endl;
			flag = itr->y < x.y;
			if(flag) {
				hull[d].erase(itr);
			}
		}else if(itr == hull[d].begin()) {
			flag = true;			
		}else {
			P b = *itr;
			itr--;
			P a = *itr;
			//cout << a.x << ' ' << b.x << ' ' << x.x << endl;
			P c{x.x, a.y + (b.y - a.y) * (x.x - a.x) / (b.x - a.x)};
			flag = x.y > c.y;

		}
		if(flag) {
			auto itr = hull[d].insert(x).fi;
			for(;;) {
				auto it2 = itr;
				it2++;
				if(it2 == hull[d].end()) break;
				auto it3 = it2;
				it3++;
				if(it3 == hull[d].end()) break;
				if((*it2 - *itr) * (*it3 - *it2) >= 0) {
					hull[d].erase(it2);
				}else {
					break;
				}
			}
			for(;;) {
				auto it2 = itr;
				if(it2 == hull[d].begin()) break;
				it2--;
				auto it3 = it2;
				if(it3 == hull[d].begin()) break;
				it3--;
				if((*it2 - *it3) * (*itr - *it2) >= 0) {
					hull[d].erase(it2);
				}else {
					break;
				}
			}
		}
		x = -1 * x;
	}
	/*printf("insert ");
	x.print();
	for(int d = 0; d < 2; d++) {
		printf("[\n");
		for(auto p : hull[d]) {
			if(d) p = -1 * p;
			p.print();
		}
		printf("---\n");
	}*/
}

D len[2];
void solve(P x) {
	if(x.y == 0) {
		D x1 = hull[0].begin()->x;
		D x2 = hull[0].rbegin()->x;
		len[0] = min(x1 * x.x, x2 * x.x);
		len[1] = max(x1 * x.x, x2 * x.x);
		return;
	}
	for(int d = 0; d < 2; d++) {
		P dir = x;
		if(dir.y < 0) {
			dir = -1 * dir;
		}

		int le = 0, ri = hull[d].size() - 1;
		while(le != ri) {
			int mid = (le + ri) / 2;

			P a = *hull[d].find_by_order(mid);
			P b = *hull[d].find_by_order(mid + 1);
			if((b - a) % dir > 0) {
				le = mid + 1;
			}else {
				ri = mid;
			}
		}
		if(d == 0) {
			len[0] = len[1] = *(hull[d].find_by_order(le)) % x;
		}else {
			D val = *(hull[d].find_by_order(le)) % x;
			len[0] = min(len[0], val);
			len[1] = max(len[1], val);
		}
		x = -1 * x;
	}
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
//n = 100000;
//m = 100000;
	for(int i = 0; i < n; i++) {
		a[i].scan();
		d[i].scan();
//a[i].rand();
//d[i].rand();
		d[i] = d[i].zoom(1);
	}
	for(int i = 0; i < m; i++) {
		P x;
		x.scan();
//x.rand();
		insert(x);
	}
	D ans = 0;
	for(int i = n - 1; i >= 0; i--) {
		solve(d[i]);
		D x = a[i] % d[i];
		
		len[0] = min(len[0], x);
		len[1] = max(len[1], x);
		/*cout << len[0] << '!' << len[1] << endl;
		a[i].print();
		d[i].print();
		((len[0] - x) * d[i]).print();
		((len[1] - x) * d[i]).print();*/
		ans += len[1] - len[0];
		
		insert(a[i] + (len[0] - x) * d[i]);
		insert(a[i] + (len[1] - x) * d[i]);
	}
	cout << setprecision(20) << ans << endl;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 4
-3 3 0.6 -0.3
4 -1 1 1
1 -4 1 0
-2 3
2 3
2 -2
-0.5 -2

output:

20.275232907551223616

result:

ok answer is 20.2752329075512  (delta 0)

Test #2:

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

input:

5 3
0.5 0.4 1 1
0.5 0.4 3 4
0.5 0.35 1 1
0.4 0.4 1 0
0.5 0.3 0 1
0.5 0.4
0.6 0.4
0.5 0.5

output:

0.85981327522309615045

result:

ok answer is 0.859813275223096  (delta 0)

Test #3:

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

input:

5 3
0.5 0.4 1 1
0.5 0.4 3 4
0.5 0.35 1 1
0.4 0.4 1 0
0.5 0.3 0 1
0.5 0.4
0.5 0.5
0.6 0.4

output:

0.85981327522309615045

result:

ok answer is 0.859813275223096  (delta 0)

Test #4:

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

input:

5 12
0.7 -0.3 0 1
0.5 0 1 1
0.5 0.033333333333333 0 1
0.5 0.033333333333333 1 0
0.5 0.05 1 0
0.0 0
0.1 0
0.2 0
0.3 0
0.4 0
0.5 0
0.5 0.1
0.6 0
0.7 0
0.8 0
0.9 0
1.0 0

output:

3.4174621202458749006

result:

ok answer is 3.41746212024588  (delta 1.2995e-16)

Test #5:

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

input:

5 12
-0.3 0.7 1 0
0 0.5 1 1
0.033333333333333 0.5 1 0
0.033333333333333 0.5 0 1
0.05 0.5 0 1
0 0.6
0 0.4
0.1 0.5
0 0.3
0 0.8
0 0.5
0 0.9
0 1.0
0 0.1
0 0.0
0 0.7
0 0.2

output:

3.4174621202458749006

result:

ok answer is 3.41746212024588  (delta 1.2995e-16)

Test #6:

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

input:

10 12
0 0 1 1
0.6 0.2 0 1
0.4 0.6 -1 0
0.6 0 -1 1
0 0 0 1
0.4 0.5 1 0
0.5 0.3 1 0
0 0.3 1 0
0.3 0.3 1 0
0.3 0.3 0 1
0.2 0.2
0.6 0.2
0.6 0.6
0.2 0.6
0.2 0.2
0.6 0.2
0.6 0.6
0.2 0.6
0.2 0.2
0.6 0.2
0.6 0.6
0.2 0.6

output:

6.0970562748477140583

result:

ok answer is 6.09705627484772  (delta 2.9135e-16)

Test #7:

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

input:

11 3
0.4 0.6 -1 1.2
0.8 -0.1 -1 0.1
0.5 1.05 0 1
0.4 1.0 0 1
0.6 1.0 0 1
0.3 0.9 0 1
0.7 0.9 0 1
0.2 0.7 0 1
0.8 0.7 0 1
0.1 0.4 0 1
0.9 0.4 0 1
0 0
1 0
0.5 -0.1

output:

10.181036773720618585

result:

ok answer is 10.1810367737206  (delta 0)

Test #8:

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

input:

8 3
-0.762220710020949 0.960848634814740 0.280390347859400 0.959886062419538
-0.543850971093615 0.734414501114893 -0.427256201232584 -0.904130598148465
-0.308587087111148 -0.723868828767586 -0.977369509658100 -0.211539219982217
-0.080679584211341 -0.623872645456952 0.831979117964964 0.55480694594628...

output:

13.026898136401997541

result:

ok answer is 13.026898136402  (delta 0)

Test #9:

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

input:

9 3
0.898690498337619 -0.179746197104477 0.999614363528218 -0.027769123646145
0.110351463328162 -0.422616723450085 -0.279788827908685 -0.960061566659912
-0.300252996136536 -0.968309581066027 0.854696098517848 -0.519128673045874
0.952829435906291 0.237672663072341 -0.611183161853922 -0.79148919301923...

output:

19.905002807773679953

result:

ok answer is 19.9050028077737  (delta 1.7848e-16)

Test #10:

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

input:

10 3
0.070342089497671 -0.460264862606530 0.571810294945788 -0.820385876642212
0.788475327551128 -0.311212069608293 0.964101929706117 -0.265532425773089
0.366813150247519 0.189414857841604 0.900950396708540 0.433922092858526
-0.025464690043421 0.481042370982425 0.621108238787538 0.783724795901114
0....

output:

21.333621812460928755

result:

ok answer is 21.3336218124609  (delta 0)

Test #11:

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

input:

11 3
-0.775122867998075 -0.324462516766419 -0.870185763377592 -0.492723794041812
0.271867294126994 -0.314788596521751 0.875220126295877 -0.483724850019750
0.159838684607629 -0.014674090173325 0.920134803351038 0.391601766673933
-0.208305526915072 0.138678278167128 -0.855854780186333 0.51721619776666...

output:

5.4815923903821252754

result:

ok answer is 5.48159239038213  (delta 1.6203e-16)

Test #12:

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

input:

12 5
0.316035625860380 0.054167102894646 0.415233195457349 -0.909715006686313
0.012033693255599 -0.517127656466508 -0.998047008109908 0.062467348293813
-0.911778006353474 0.434138159295005 -0.826906371022239 0.562339624748987
0.591762739510491 -0.252317701851837 -0.881901192154716 0.471434287336094
...

output:

20.423831191837824601

result:

ok answer is 20.4238311918378  (delta 1.7395e-16)

Test #13:

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

input:

15 7
0.383636462970281 0.091301273291054 -0.178083033367321 -0.984015463916443
0.028282065271478 -0.787867919130403 0.750256053487245 -0.661147377069398
0.149903266403460 0.601903906070213 0.428442456521616 0.903569068444534
0.093087745686689 0.006815105251976 0.803797260834196 -0.594903322797447
-0...

output:

5.7504268960373329028

result:

ok answer is 5.75042689603733  (delta 1.5445e-16)

Test #14:

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

input:

100 3
-0.578211107831801 0.287473638423979 0.834386001175380 0.551180552126577
-0.536512988104892 0.460257895201809 -0.429955857196671 -0.902849910484725
0.659448545647913 -0.913615255033808 0.093581854933560 0.995611589138653
-0.796157342487406 0.263458009987518 -0.997872466743782 -0.06519616641091...

output:

104.44401831208326033

result:

ok answer is 104.444018312083  (delta 4.0819e-16)

Test #15:

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

input:

100 100
-0.174467648909083 -0.201801252266503 0.470131387603037 0.882596441410480
-0.472138238030407 -0.453553930266106 0.351835966244485 0.936061671502903
-0.688261644623982 -0.268241883678908 -0.148633790169310 -0.988892307796914
0.380541159594408 0.161158290178969 -0.474254880064852 -0.8803875900...

output:

295.94065105400369184

result:

ok answer is 295.940651054004  (delta 3.8415e-16)

Test #16:

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

input:

100 5
0.743611279083013 0.006283944783222 0.667348844117210 -0.744745272059799
0.006486241371740 0.143827295110092 -0.880291809849029 0.474432639594622
-0.311493926810460 0.755585693216458 -0.375884911761184 0.926666354795666
0.139232497699456 0.557448352048095 -0.988388963963009 0.151944910793776
0...

output:

107.34246515548245307

result:

ok answer is 107.342465155483  (delta 3.9716e-16)

Test #17:

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

input:

1000 3
0.814193108063829 0.938268846693299 0.189021563160450 -0.981972936826866
-0.894462915658156 0.056567325082831 -0.603914948132540 -0.797048766025060
0.850406232867379 0.328000667703139 0.426841712270211 0.904326352964589
0.409208076792267 0.609529714382619 -0.797872175099292 -0.602826668456468...

output:

2502.7027790773883487

result:

ok answer is 2502.70277907739  (delta 3.634e-16)

Test #18:

score: 0
Accepted
time: 32ms
memory: 6256kb

input:

10000 3
-0.027344576727362 0.366422341172134 0.380069695570397 0.924957851206759
-0.036905642095206 0.485758207930430 0.688750742833412 -0.724998216719478
0.984393996844049 0.730489810857773 0.719598128519330 -0.694390764218158
0.770266818005228 -0.799441248474411 -0.946212639196676 0.32354542405118...

output:

48234.327763780021172

result:

ok answer is 48234.3277637802  (delta 3.0169e-15)

Test #19:

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

input:

1000 1000
0.409735024061885 0.151845763225521 0.773343465013364 0.633987290977606
-0.752839887714774 -0.843860968010812 0.524959030774212 0.851127496917236
0.670481080838583 -0.696163386521161 0.933753290400254 -0.357917298641318
0.444963577857897 -0.976462799285448 0.514989081978322 0.8571967367198...

output:

10299.709268273264021

result:

ok answer is 10299.7092682733  (delta 2.2959e-15)

Test #20:

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

input:

10000 10000
-0.450025351735280 -0.090008923269524 -0.722784354286953 0.691073640937052
0.704498372588649 -0.468600464166860 0.981463972996210 0.191646731541381
-0.325206146833855 0.469882180672171 0.992134534816577 0.125176135202735
-0.532144632997687 0.346217231979403 0.813791044230086 -0.581157583...

output:

57702.951696786930295

result:

ok answer is 57702.951696787  (delta 1.6392e-15)

Test #21:

score: 0
Accepted
time: 8ms
memory: 6160kb

input:

1000 1000
0.961556216429425 -1.314762670245720 0.920163091307436 -0.946420876792685
0.327847561600822 1.689778414181223 0.489605901837277 0.293585039663264
1.527710134662603 -0.903485255055727 0.674735734675436 -0.748453599212006
-1.193128488735113 0.999735066938836 -0.632026828273573 -0.93181050745...

output:

2014.12457730204449

result:

ok answer is 2014.12457730204  (delta 1.9191e-15)

Test #22:

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

input:

300 200
-0.500000000000000 1.000000000000000 1.000000000000000 0.000000000000000
-0.500000000000000 -0.500000000000000 1.000000000000000 0.000000000000000
0.121595097389671 -0.500000000000000 0.000000000000000 -1.000000000000000
-0.235498049472471 0.764501950527529 0.707106781186548 -0.7071067811865...

output:

436.8746750430835433

result:

ok answer is 436.874675043085  (delta 2.4722e-15)

Test #23:

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

input:

300 200
0.967399888013902 -0.334791316950851 0.310921244942051 0.950435678751427
-0.458253630113238 0.131590550462226 -0.310921244942051 -0.950435678751427
0.015560888789305 -0.024581562690774 -0.452204992813285 0.891914034240261
0.796412381165649 -0.779384447833368 0.891914034240261 0.4522049928132...

output:

437.0462479183377012

result:

ok answer is 437.046247918338  (delta 1.6908e-15)

Test #24:

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

input:

100 100
-0.199403905909808 0.022355344270012 -0.837983463329530 0.545695625038580
-0.041955209049741 0.123173830866749 0.522771485664286 0.852472858087784
-0.108886336042388 0.148682670553837 -0.185957756356147 0.982557740212242
-0.102620671109980 0.149079785673387 0.096581833909079 0.99532504708701...

output:

83.326051444803912807

result:

ok answer is 83.3260514448039  (delta 1.7055e-16)

Test #25:

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

input:

1000 10
-0.030267924544199 -0.426227633151606 0.829000748513003 0.559247493481089
-0.204597859638700 0.387349737682089 0.997998678833624 -0.063234777190576
-0.036529678885983 -0.416866144465642 -0.839013778744419 -0.544110171819100
-0.041740249951155 -0.408535174899693 0.854780863223727 0.5189890903...

output:

2656.2981033195940235

result:

ok answer is 2656.29810331959  (delta 1.712e-16)

Test #26:

score: 0
Accepted
time: 1566ms
memory: 28872kb

input:

100000 100000
0.287607924171659 0.957748235160822 0.287607924171659 0.957748235160822
-0.587124239805137 0.809496835715397 -0.587124239805137 0.809496835715397
0.235735806381417 -0.971817179097850 0.235735806381417 -0.971817179097850
-0.995463865110344 -0.095140387110710 -0.995463865110344 -0.095140...

output:

199999.99998175257815

result:

ok answer is 199999.999968388  (delta 6.6823e-11)

Test #27:

score: 0
Accepted
time: 1530ms
memory: 28936kb

input:

100000 100000
1.471947842183454 0.629734570970794 0.747683235881579 0.581473261498088
-1.215615714218694 0.580256542669015 0.436134180069619 -0.160606494997628
0.684413453640551 -1.086518887281310 0.431196251174890 0.450527822681312
1.477680966543098 0.294025539461242 -0.738362648707372 -0.535047787...

output:

200005.1450324169642

result:

ok answer is 200005.145019187  (delta 6.6148e-11)

Test #28:

score: 0
Accepted
time: 511ms
memory: 10140kb

input:

100000 100000
-0.177688296351407 -0.411712111497956 0.791140251966530 0.611634778048416
0.919580950063656 -0.406448760627006 0.529466659578948 0.848330747052298
-0.008332939209265 0.192508647044135 -0.545370524743876 -0.838195079167487
-0.532323429468533 0.578933005319365 0.233707559802554 -0.972306...

output:

1268959.2337925268215

result:

ok answer is 1268959.23379253  (delta 9.1741e-16)

Test #29:

score: 0
Accepted
time: 355ms
memory: 10152kb

input:

100000 100000
-0.500000000000000 1.000000000000000 1.000000000000000 0.000000000000000
-0.500000000000000 -0.500000000000000 -1.000000000000000 0.000000000000000
0.684927610017092 0.815072389982908 -0.707106781186548 -0.707106781186548
-0.211357035216055 -0.288642964783945 -0.707106781186548 -0.7071...

output:

145707.93295265071202

result:

ok answer is 145707.932952596  (delta 3.7691e-13)

Test #30:

score: 0
Accepted
time: 439ms
memory: 10148kb

input:

100000 100000
1.577117650292472 0.201543534619925 -0.191892109156045 -0.981416027199294
0.104993609493531 0.489381698353992 0.191892109156045 0.981416027199294
0.373333186973227 -1.091489414908930 -0.191892109156045 -0.981416027199294
1.184033282757534 -0.915255598852457 -0.558277716357353 0.8296541...

output:

145709.99182715398446

result:

ok answer is 145709.991827097  (delta 3.9408e-13)

Test #31:

score: 0
Accepted
time: 470ms
memory: 17044kb

input:

80000 80000
0.099106929619117 -0.086466539443792 0.409996826361186 -0.912086948910988
0.427060557793502 0.147562642147517 -0.669301963709056 0.742990498845848
-0.863025460538809 0.012640739936928 -0.957072065152402 0.289850068319667
-0.149591807669463 -0.157745746761316 -0.187289479369577 0.98230476...

output:

1123464.9257492992422

result:

ok answer is 1123464.92574865  (delta 5.8152e-13)

Test #32:

score: 0
Accepted
time: 479ms
memory: 17256kb

input:

80000 80000
-1.108048173106791 0.725400926971845 -0.672378936988972 0.740207109594052
-0.206152612101677 -0.827852884471091 0.302935778678867 -0.953010972652586
-0.403437915294586 0.805362571629397 -0.623994424018216 -0.781428793169393
-0.374709398944905 0.781457387058594 0.662355433571538 0.7491897...

output:

2545229.1926034828621

result:

ok answer is 2545229.19260322  (delta 1.0154e-13)