QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#347551 | #7527. Doors of the Wardrobe | ucup-team1209 | AC ✓ | 561ms | 46756kb | C++20 | 3.6kb | 2024-03-09 14:14:19 | 2024-03-09 14:14:20 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
void IOinit() {
std::ios::sync_with_stdio(false), cin.tie(0);
#ifdef zqj
freopen("1.in", "r", stdin);
#endif
}
int n, m;
using db = long double;
struct vec2 {
db x, y;
db norm() const { return x * x + y * y; }
} zero;
vec2 operator + (vec2 x, vec2 y) { return {x.x + y.x, x.y + y.y}; }
vec2 operator - (vec2 x, vec2 y) { return {x.x - y.x, x.y - y.y}; }
vec2 operator * (vec2 x, db y) { return {x.x * y, x.y * y}; }
db operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
db operator % (vec2 x, vec2 y) { return x.x * y.x + x.y * y.y; }
const db eps = 1e-13;
db sgn(db x) {
return x < -eps ? -1 : x > eps;
}
db eql(db x, db y) {
return sgn(x - y) == 0;
}
db cross(vec2 x, vec2 y, vec2 z) {
return (y - x) * (z - x);
}
std::vector<vec2> gethull(std::vector<vec2> o) {
iter_swap(o.begin(), min_element(o.begin(), o.end(), [](vec2 x, vec2 y) {
return eql(x.x, y.x) ? x.y < y.y : x.x < y.x;
}));
sort(o.begin() + 1, o.end(), [&](vec2 x, vec2 y) {
db c = (x - o[0]) * (y - o[0]);
if(fabs(c) > eps) return c > 0;
return (x - o[0]).norm() < (y - o[0]).norm();
});
o.erase(remove_if(o.begin() + 1, o.end(), [&](vec2 x) {
return sqrt((x - o[0]).norm()) < eps;
}), o.end());
std::vector<vec2> stack;
for(vec2 x : o) {
for(; stack.size() >= 2 && cross(stack.rbegin()[1], stack.back(), x) <= eps;) {
stack.pop_back();
}
stack.push_back(x);
}
for(; stack.size() > 2 && cross(stack.rbegin()[1], stack.back(), o[0]) <= eps;) {
stack.pop_back();
}
return stack;
}
db findmax(vec2 d, const std :: vector <vec2> & a) {
int l = 0, r = a.size() - 1;
if(a[0] % d > a.back() % d) {
for( ; l + 1 < r; ) {
int mid = (l + r) >> 1;
if(a[mid] % d > a[l] % d && a[mid] % d > a[mid - 1] % d) {
l = mid;
}
else {
r = mid;
}
}
return a[l] % d;
}
else {
for(; l + 1 < r; ) {
int mid = (l + r) >> 1;
if(a[mid] % d > a[r] % d && a[mid] % d > a[mid + 1] % d) {
r = mid;
}
else {
l = mid;
}
}
return a[r] % d;
}
}
const int N = 200005;
vec2 p[N];
vec2 v[N];
vec2 L[N], R[N];
db l[N], r[N];
db ans = 0;
void solve(int l, int r) {
if(l + 1 == r) {
int i = l;
auto & l = ::l;
auto & r = ::r;
l[i] -= p[i] % v[i];
r[i] -= p[i] % v[i];
R[i] = p[i] + v[i] * r[i];
L[i] = p[i] + v[i] * l[i];
ans += r[i] - l[i];
return ;
}
int mid = (l + r) >> 1;
solve(mid, r);
std::vector<vec2> o;
for(int i = mid;i < r;++i) {
o.push_back(L[i]);
o.push_back(R[i]);
}
o = gethull(o);
for(int i = l;i < mid;++i) {
::r[i] = std::max(::r[i], findmax(v[i], o));
::l[i] = std::min(::l[i], -findmax(zero-v[i], o));
}
solve(l, mid);
}
db get(char * c) {
int x = 0, flg = 1;
if(*c == '-') flg = -1, ++c;
for(;*c && *c != '.';++c) x = x * 10 + (*c & 15);
if(*c == '.') {
double p = 0.1, sum = 0;
for(;*++c;) {
sum += p * (*c & 15);
p *= 0.1;
}
return (sum + x) * flg;
} else {
return x * flg;
}
}
vec2 get() {
static char ch[100000];
cin >> ch;
db x = get(ch);
cin >> ch;
db y = get(ch);
return {x, y};
}
int main() {
IOinit();
cin >> n >> m;
for(int i = 0;i < n;++i) {
p[i] = get();
v[i] = get();
v[i] = v[i] * (1 / std::sqrt(v[i].norm()));
}
std::vector<vec2> o(m);
for(int i = 0;i < m;++i) {
o[i] = get();
}
o = gethull(o);
for(int i = 0;i < n;++i) {
l[i] = r[i] = p[i] % v[i];
r[i] = std::max(r[i], findmax(v[i], o));
l[i] = std::min(l[i], -findmax(zero-v[i], o));
}
solve(0, n);
printf("%.20Lf\n", ans);
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 14192kb
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.27523290755122361596
result:
ok answer is 20.2752329075512 (delta 0)
Test #2:
score: 0
Accepted
time: 0ms
memory: 14160kb
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.85981327522309614899
result:
ok answer is 0.859813275223096 (delta 0)
Test #3:
score: 0
Accepted
time: 2ms
memory: 14380kb
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.85981327522309614899
result:
ok answer is 0.859813275223096 (delta 0)
Test #4:
score: 0
Accepted
time: 2ms
memory: 14152kb
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.41746212024587496222
result:
ok answer is 3.41746212024588 (delta 1.2995e-16)
Test #5:
score: 0
Accepted
time: 0ms
memory: 14284kb
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.41746212024587496222
result:
ok answer is 3.41746212024588 (delta 1.2995e-16)
Test #6:
score: 0
Accepted
time: 1ms
memory: 14156kb
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.09705627484771499856
result:
ok answer is 6.09705627484772 (delta 1.4567e-16)
Test #7:
score: 0
Accepted
time: 0ms
memory: 14048kb
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.18103677372061888207
result:
ok answer is 10.1810367737206 (delta 0)
Test #8:
score: 0
Accepted
time: 1ms
memory: 14388kb
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.02689813640199958250
result:
ok answer is 13.026898136402 (delta 1.3636e-16)
Test #9:
score: 0
Accepted
time: 1ms
memory: 14212kb
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.90500280777368100060
result:
ok answer is 19.9050028077737 (delta 1.7848e-16)
Test #10:
score: 0
Accepted
time: 0ms
memory: 14288kb
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.33362181246093060641
result:
ok answer is 21.3336218124609 (delta 0)
Test #11:
score: 0
Accepted
time: 1ms
memory: 14256kb
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.48159239038212576720
result:
ok answer is 5.48159239038213 (delta 0)
Test #12:
score: 0
Accepted
time: 1ms
memory: 14256kb
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.42383119183782357042
result:
ok answer is 20.4238311918378 (delta 1.7395e-16)
Test #13:
score: 0
Accepted
time: 1ms
memory: 14164kb
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.75042689603733355461
result:
ok answer is 5.75042689603733 (delta 1.5445e-16)
Test #14:
score: 0
Accepted
time: 1ms
memory: 14176kb
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.44401831208327238038
result:
ok answer is 104.444018312083 (delta 5.4425e-16)
Test #15:
score: 0
Accepted
time: 0ms
memory: 14304kb
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.94065105400371587518
result:
ok answer is 295.940651054004 (delta 3.8415e-16)
Test #16:
score: 0
Accepted
time: 1ms
memory: 14060kb
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.34246515548247163929
result:
ok answer is 107.342465155483 (delta 2.6478e-16)
Test #17:
score: 0
Accepted
time: 3ms
memory: 14436kb
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.70277907738873146570
result:
ok answer is 2502.70277907739 (delta 1.817e-16)
Test #18:
score: 0
Accepted
time: 27ms
memory: 14796kb
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.32776378002951389590
result:
ok answer is 48234.3277637802 (delta 2.8661e-15)
Test #19:
score: 0
Accepted
time: 4ms
memory: 14364kb
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.70926827326490293757
result:
ok answer is 10299.7092682733 (delta 2.1193e-15)
Test #20:
score: 0
Accepted
time: 36ms
memory: 18760kb
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.95169678694118786666
result:
ok answer is 57702.951696787 (delta 1.387e-15)
Test #21:
score: 0
Accepted
time: 0ms
memory: 14324kb
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.12457730204459349643
result:
ok answer is 2014.12457730204 (delta 1.9191e-15)
Test #22:
score: 0
Accepted
time: 3ms
memory: 14260kb
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.87467504308359914078
result:
ok answer is 436.874675043085 (delta 2.342e-15)
Test #23:
score: 0
Accepted
time: 0ms
memory: 14248kb
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.04624791833760097393
result:
ok answer is 437.046247918338 (delta 1.9509e-15)
Test #24:
score: 0
Accepted
time: 2ms
memory: 16256kb
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.32605144480392544981
result:
ok answer is 83.3260514448039 (delta 3.4109e-16)
Test #25:
score: 0
Accepted
time: 3ms
memory: 14160kb
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.29810331959437652571
result:
ok answer is 2656.29810331959 (delta 1.712e-16)
Test #26:
score: 0
Accepted
time: 561ms
memory: 46756kb
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.99997208477434185170
result:
ok answer is 199999.999968388 (delta 1.8484e-11)
Test #27:
score: 0
Accepted
time: 556ms
memory: 42888kb
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.14502273830318301862
result:
ok answer is 200005.145019187 (delta 1.7756e-11)
Test #28:
score: 0
Accepted
time: 456ms
memory: 33068kb
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.23379252702204667003
result:
ok answer is 1268959.23379253 (delta 1.1009e-15)
Test #29:
score: 0
Accepted
time: 396ms
memory: 37936kb
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.93295265076304190188
result:
ok answer is 145707.932952596 (delta 3.7731e-13)
Test #30:
score: 0
Accepted
time: 375ms
memory: 33080kb
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.99182715398690390884
result:
ok answer is 145709.991827097 (delta 3.9408e-13)
Test #31:
score: 0
Accepted
time: 372ms
memory: 33324kb
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.92574929964712282526
result:
ok answer is 1123464.92574865 (delta 5.8173e-13)
Test #32:
score: 0
Accepted
time: 384ms
memory: 33452kb
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.19260348284296924248
result:
ok answer is 2545229.19260322 (delta 1.0154e-13)