QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#368295 | #8513. Insects, Mathematics, Accuracy, and Efficiency | Jose_17 | WA | 37ms | 4280kb | C++20 | 7.2kb | 2024-03-26 23:10:33 | 2024-03-26 23:10:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// Holi c:
#define ll long long int
//#define ld long double
#define ii __int128
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
const int Inf = 1e9;
const ll mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 5;
using ld = long double;
const ld eps = 1e-9, inf = numeric_limits<ld>::max(), pi = acos(-1);
// For use with integers, just set eps=0 and everything remains the same
bool geq(ld a, ld b){return a-b >= -eps;} //a >= b
bool leq(ld a, ld b){return b-a >= -eps;} //a <= b
bool ge(ld a, ld b){return a-b > eps;} //a > b
bool le(ld a, ld b){return b-a > eps;} //a < b
bool eq(ld a, ld b){return abs(a-b) <= eps;} //a == b
bool neq(ld a, ld b){return abs(a-b) > eps;} //a != b
struct point{
ld x, y;
point(): x(0), y(0){}
point(ld x, ld y): x(x), y(y){}
point operator+(const point & p) const{return point(x + p.x, y + p.y);}
point operator-(const point & p) const{return point(x - p.x, y - p.y);}
point operator*(const ld & k) const{return point(x * k, y * k);}
point operator/(const ld & k) const{return point(x / k, y / k);}
point operator+=(const point & p){*this = *this + p; return *this;}
point operator-=(const point & p){*this = *this - p; return *this;}
point operator*=(const ld & p){*this = *this * p; return *this;}
point operator/=(const ld & p){*this = *this / p; return *this;}
point rotate(const ld & a) const{return point(x*cos(a) - y*sin(a), x*sin(a) + y*cos(a));}
point perp() const{return point(-y, x);}
ld ang() const{
ld a = atan2l(y, x); a += le(a, 0) ? pi * 2 : 0;
return a;
}
ld ang(const point & p) const{ return abs(ang() - p.ang()); }
ld dot(const point & p) const{return x * p.x + y * p.y;}
ld cross(const point & p) const{return x * p.y - y * p.x;}
ld norm() const{return x * x + y * y;}
ld length() const{return sqrtl(x * x + y * y);}
point unit() const{return (*this) / length();}
bool operator==(const point & p) const{return eq(x, p.x) && eq(y, p.y);}
bool operator!=(const point & p) const{return !(*this == p);}
bool operator<(const point & p) const{return le(x, p.x) || (eq(x, p.x) && le(y, p.y));}
bool operator>(const point & p) const{return ge(x, p.x) || (eq(x, p.x) && ge(y, p.y));}
bool half(const point & p) const{return le(p.cross(*this), 0) || (eq(p.cross(*this), 0) && le(p.dot(*this), 0));}
};
ostream &operator<<(ostream &os, const point & p){return os << "(" << p.x << ", " << p.y << ")";}
int sgn(ld x){
if(ge(x, 0)) return 1;
if(le(x, 0)) return -1;
return 0;
}
void polarSort(vector<point> & P, const point & o, const point & v){
//sort points in P around o, taking the direction of v as first angle
sort(P.begin(), P.end(), [&](const point & a, const point & b){
return point((a - o).half(v), 0) < point((b - o).half(v), (a - o).cross(b - o));
});
}
vector<point> convexHull(vector<point> P){
sort(P.begin(), P.end());
vector<point> L, U;
for(int i = 0; i < P.size(); i++){
while(L.size() >= 2 && leq((L[L.size() - 2] - P[i]).cross(L[L.size() - 1] - P[i]), 0)){
L.pop_back();
}
L.push_back(P[i]);
}
for(int i = P.size() - 1; i >= 0; i--){
while(U.size() >= 2 && leq((U[U.size() - 2] - P[i]).cross(U[U.size() - 1] - P[i]), 0)){
U.pop_back();
}
U.push_back(P[i]);
}
L.pop_back();
U.pop_back();
L.insert(L.end(), U.begin(), U.end());
return L;
}
ld area(vector<point> & P){
int n = P.size();
ld ans = 0;
for(int i = 0; i < n; i++){
ans += P[i].cross(P[(i + 1) % n]);
}
return abs(ans / 2);
}
vector<point> intersectLineCircle(const point & a, const point & v, const point & c, ld r){
//line a+tv, circle with center c and radius r
ld h2 = r*r - v.cross(c - a) * v.cross(c - a) / v.norm();
point p = a + v * v.dot(c - a) / v.norm();
if(eq(h2, 0)) return {p}; //line tangent to circle
else if(le(h2, 0)) return {}; //no intersection
else{
point u = v.unit() * sqrt(h2);
return {p - u, p + u}; //two points of intersection (chord)
}
}
ld f1(point p0, point p1, point p2){
return abs((p1 - p0).cross(p2 - p0)) / 2;
}
ld f(point p0, point p1, point t1, point t2){
ld ans = 0, l = 0, r = 0;
//r = (p0).ang(p1);
r = acosl(p1.dot(p0) / p1.length() / p0.length());
point rt = p1.rotate(r);
if(!(abs(rt.x - p0.x) <= 0.5 && abs(rt.y - p0.y) <= 0.5)) r = 2 * pi - r;
//cout<<r<<'\n';
for(int i = 0; i < 100; i++){
ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
ld w1 = f1(t1, t2, p1.rotate(m1)), w2 = f1(t1, t2, p1.rotate(m2));
if(w1 < w2) l = m1;
else r = m2;
}
return f1(t1, t2, p1.rotate(l));
}
ld calc(point p0, point p1, int t0, int t1, vector<point> & v){
ld ans = f(p0, p1, v[t0], v[t1]);
return ans;
}
ld solveto2(point p0, point p1, point p2, point p3){
return max(f(p0, p1, p2, p3), f(p1, p0, p3, p2));
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
int n; ld r; cin>>n>>r; r += eps;
vector<point> v(n);
for(int i = 0; i < n; i++){ int a, b; cin>>a>>b; v[i] = point(a, b); }
if(n == 1){ cout<<0<<'\n'; return 0; }
sort(all(v));
v = convexHull(v); n = v.size(); ld res = area(v); reverse(all(v));
vector<point> side;
for(int i = 0; i < v.size(); i++){
auto u = intersectLineCircle(v[i], v[(i + 1) % (int)v.size()] - v[i], point(0, 0), r);
if(n == 2 && i + 1 == v.size()) continue;
side.pb(u[0]); side.pb(u[1]);
}
polarSort(side, point(0, 0), point(-1, 0));
reverse(all(side)); vector<point> u; u.pb(v[v.size() - 1]); for(int i = 0; i < v.size() - 1; i++) u.pb(v[i]); v = u;
//for(auto e : side) cout<<e<<" | "; cout<<'\n'<<"-------------"<<'\n';
//for(auto e : v) cout<<e<<" | "; cout<<'\n'<<"--------------------------------"<<'\n';
int j = 0, l = 0, m = side.size(); n = v.size(); ld ans = 0, zes = 0;
if(n == 2){ cout<<setprecision(20)<<solveto2(side[0], side[1], v[0], v[1])<<'\n'; return 0; }
//Obtener las tangentes de cada intervalo
for(int i = 0; i < m; i++){
//if(side[i] == side[(i + 1) % m]) continue;
while((v[l] - side[i]).cross(v[(l + 1) % n] - side[i]) < eps){
if(i) zes -= f1(v[j], v[l], v[(l + 1) % n]);
l++; if(l == n) l = 0;
}
//cout<<zes<<" v ";
if(!i) j = (l + 1) % n;
while((v[j] - side[(i + 1) % m]).cross(v[(j + 1) % n] - side[(i + 1) % m]) > -eps){
zes += f1(v[l], v[j], v[(j + 1) % n]);
j++; if(j == n) j = 0;
}
if(abs((v[j] - side[(i + 1) % m]).cross(v[(j - 1 + n) % n] - side[(i + 1) % m])) <= eps){
j--;
if(j < 0) j += n;
zes -= f1(v[l], v[j], v[(j + 1) % n]);
}
zes = 0; int l1 = l;
while((l1 + 1) % n != j){
zes += f1(v[l1], v[(l1 + 1) % n], v[j]);
l1++; if(l1 == n) l1 = 0;
}
//cout<<zes<<'\n';
//cout<<"Intervalo: "<<side[i]<<" , "<<side[(i + 1) % m]<<" Con las tangentes en: "<<v[l]<<" , "<<v[j]<<" Con area de "<<calc(side[i], side[(i + 1) % m], l, j, v)<<" , "<<zes<<'\n';
ans = max(ans, calc(side[i], side[(i + 1) % m], l, j, v) - abs(zes));
//cout<<res+ans<<'\n';
}
cout<<setprecision(20)<<res + ans;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
input:
4 1000 -1000 0 0 0 1000 0 0 -1000
output:
2000000.0000009999999
result:
ok found '2000000.000001000', expected '2000000.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
2 100 17 7 19 90
output:
4849.7046444790757871
result:
ok found '4849.704644479', expected '4849.704644438', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
1 100 13 37
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3832kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
2240000.0000008
result:
ok found '2240000.000000800', expected '2240000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
3 1000 200 400 -600 -400 400 -800
output:
1045685.4249498037049
result:
ok found '1045685.424949804', expected '1045685.424949238', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
4 1000 200 -600 600 -400 800 -600 0 -800
output:
732310.56256217836551
result:
ok found '732310.562562178', expected '732310.562561766', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
4 1000 -600 700 -300 900 0 800 -800 400
output:
892213.59550040515285
result:
ok found '892213.595500405', expected '892213.595499958', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
5 1000 -300 -200 -200 -400 -100 -700 -800 -500 -500 -300
output:
619005.49446438991902
result:
ok found '619005.494464390', expected '619005.494464026', error '0.000000000'
Test #9:
score: 0
Accepted
time: 23ms
memory: 3980kb
input:
1000 10000 -9998 -136 -9996 -245 -9995 -280 -9993 -347 -9991 -397 -9989 -440 -9985 -525 -9984 -545 -9983 -564 -9981 -599 -9979 -632 -9973 -721 -9971 -747 -9966 -810 -9963 -846 -9957 -916 -9953 -958 -9948 -1008 -9945 -1037 -9938 -1103 -9927 -1196 -9920 -1253 -9913 -1308 -9908 -1346 -9891 -1465 -9874 ...
output:
314026591.78011061533
result:
ok found '314026591.780110598', expected '314026591.780110359', error '0.000000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
2 10000 -9999 0 -9998 -1
output:
12070.56781186618235
result:
ok found '12070.567811866', expected '12070.567811865', error '0.000000000'
Test #11:
score: 0
Accepted
time: 37ms
memory: 4280kb
input:
1604 10000 2604 -9655 7380 -6748 9963 859 9843 1765 -1452 9894 -2024 9793 -8862 4633 -2604 -9655 9301 3673 9871 -1601 -565 -9984 9640 -2659 9312 3645 -8291 -5591 7879 6158 1301 9915 509 9987 7757 -6311 -9301 -3673 7702 -6378 5415 8407 -9971 761 9023 -4311 -6785 7346 -9852 1714 -9788 -2048 9819 -1894...
output:
314156571.11235000452
result:
ok found '314156571.112349987', expected '314156571.112349927', error '0.000000000'
Test #12:
score: 0
Accepted
time: 35ms
memory: 4116kb
input:
1444 10000 3378 8342 -734 8970 -3168 8424 1741 8830 -3631 8235 -6622 -6095 8605 -2637 -3762 8176 -8509 2932 -8915 1234 -1919 -8793 -7663 -4720 3040 -8471 -7357 5184 5746 -6927 5827 -6859 6519 6205 328 -8994 -5282 7287 4797 -7615 -5505 7120 -2733 8575 6902 5776 -4666 7696 6946 5723 -4154 7984 6644 60...
output:
257163269.62953441832
result:
ok found '257163269.629534423', expected '257163269.629530489', error '0.000000000'
Test #13:
score: 0
Accepted
time: 35ms
memory: 3996kb
input:
1396 10000 -5817 -5492 -692 -7970 -6967 -3932 -6316 -4910 -6562 4576 -7358 3140 2376 7639 -7883 1363 -2337 7651 -6950 -3962 -6927 4002 4961 -6276 5036 6216 7274 3330 -6976 3916 1490 7860 -2816 7488 -6927 -4002 -3107 7372 -6802 4211 4353 6712 -5594 -5719 875 -7952 -2943 7439 -4672 6494 -4405 -6678 -3...
output:
207875930.50000480001
result:
ok found '207875930.500004798', expected '207875930.500000000', error '0.000000000'
Test #14:
score: 0
Accepted
time: 32ms
memory: 4088kb
input:
1252 10000 -6409 2815 5515 4311 6506 2583 4459 5396 2493 6541 -3215 6218 2911 -6366 0 -7000 658 6969 312 -6993 -1100 -6913 6621 2272 -1081 -6916 -6901 1173 -658 6969 5227 -4656 2911 6366 6715 -1977 3812 5871 1015 -6926 6061 3502 -473 6984 5079 -4817 614 -6973 -2667 6472 1446 6849 -1791 -6767 -2004 -...
output:
164951741.65765937167
result:
ok found '164951741.657659382', expected '164951741.657654375', error '0.000000000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3960kb
input:
42 10000 -800 -8 -799 -40 -730 -247 -599 -399 -591 -406 -541 -443 -283 -562 -189 -584 -43 -600 223 -577 507 -464 575 -417 607 -391 654 -346 677 -320 775 -149 794 -74 726 251 718 264 698 292 689 304 619 380 538 443 331 546 315 551 279 562 237 573 182 584 116 593 52 598 -37 599 -57 598 -238 573 -314 5...
output:
8755559.4805076843531
result:
ok found '8755559.480507685', expected '8755559.480506888', error '0.000000000'
Test #16:
score: 0
Accepted
time: 4ms
memory: 3992kb
input:
171 10000 -800 -29 -794 -79 -788 -108 -785 -120 -776 -149 -775 -152 -768 -171 -748 -215 -745 -221 -738 -234 -709 -280 -704 -287 -695 -299 -688 -308 -679 -319 -667 -333 -660 -341 -631 -370 -607 -392 -593 -404 -583 -412 -564 -427 -546 -440 -527 -453 -458 -493 -422 -511 -378 -530 -360 -537 -329 -548 -2...
output:
8773418.7784269336098
result:
ok found '8773418.778426934', expected '8773418.778426135', error '0.000000000'
Test #17:
score: 0
Accepted
time: 5ms
memory: 3972kb
input:
202 10000 -900 -43 -898 -70 -895 -103 -894 -111 -890 -140 -888 -152 -873 -223 -868 -242 -862 -263 -856 -281 -835 -339 -826 -360 -812 -391 -805 -405 -793 -428 -788 -437 -780 -451 -768 -471 -757 -489 -743 -510 -731 -527 -707 -559 -692 -577 -673 -599 -664 -609 -652 -622 -621 -653 -607 -666 -596 -676 -5...
output:
10316038.315567662043
result:
ok found '10316038.315567663', expected '10316038.315566765', error '0.000000000'
Test #18:
score: 0
Accepted
time: 7ms
memory: 3972kb
input:
252 10000 -900 -43 -899 -60 -898 -73 -897 -84 -893 -120 -888 -153 -884 -174 -881 -189 -879 -198 -874 -219 -869 -238 -867 -245 -859 -272 -852 -293 -846 -310 -839 -329 -830 -351 -824 -365 -820 -374 -810 -395 -802 -411 -793 -428 -783 -446 -769 -470 -758 -487 -745 -507 -734 -523 -717 -546 -710 -555 -687...
output:
10316182.050691495266
result:
ok found '10316182.050691495', expected '10316182.050690599', error '0.000000000'
Test #19:
score: 0
Accepted
time: 10ms
memory: 3932kb
input:
404 10000 -4997 -198 -4993 -282 -4982 -433 -4975 -509 -4967 -582 -4962 -623 -4933 -821 -4925 -868 -4915 -924 -4898 -1009 -4881 -1089 -4872 -1128 -4863 -1166 -4838 -1266 -4815 -1351 -4802 -1397 -4779 -1473 -4754 -1552 -4693 -1728 -4666 -1799 -4627 -1898 -4619 -1917 -4592 -1981 -4537 -2104 -4516 -2149...
output:
95669905.97263644763
result:
ok found '95669905.972636446', expected '95669905.972632110', error '0.000000000'
Test #20:
score: 0
Accepted
time: 21ms
memory: 4252kb
input:
888 10000 -9119 -134 -9118 -188 -9117 -234 -9116 -268 -9114 -330 -9113 -357 -9108 -467 -9106 -505 -9102 -573 -9098 -634 -9096 -661 -9092 -714 -9087 -775 -9076 -895 -9070 -953 -9066 -990 -9060 -1044 -9053 -1101 -9045 -1166 -9042 -1190 -9039 -1213 -9030 -1278 -9013 -1393 -9002 -1462 -8996 -1498 -8986 ...
output:
263523679.50842037995
result:
ok found '263523679.508420378', expected '263523679.508416623', error '0.000000000'
Test #21:
score: 0
Accepted
time: 6ms
memory: 3900kb
input:
333 10000 -832 -233 -844 -216 -846 -213 -854 -201 -860 -192 -865 -184 -868 -179 -871 -173 -873 -169 -877 -161 -878 -159 -879 -157 -887 -140 -894 -122 -895 -119 -896 -116 -898 -109 -902 -94 -906 -73 -909 -56 -910 -49 -911 -40 -913 -17 -914 -3 -913 20 -909 74 -908 86 -907 94 -905 109 -902 129 -900 142...
output:
9914565.5701125531459
result:
ok found '9914565.570112552', expected '9914565.570111660', error '0.000000000'
Test #22:
score: 0
Accepted
time: 7ms
memory: 3860kb
input:
414 10000 107 794 158 789 201 784 225 781 238 779 254 776 259 775 264 774 278 771 287 769 304 765 308 764 324 760 328 759 332 758 343 755 350 753 385 743 399 739 409 736 419 733 446 724 452 722 463 718 498 705 514 699 522 696 535 691 561 681 566 679 579 673 587 669 589 668 591 667 601 662 605 660 61...
output:
10783650.25660562254
result:
ok found '10783650.256605623', expected '10783650.256604670', error '0.000000000'
Test #23:
score: 0
Accepted
time: 7ms
memory: 4176kb
input:
666 10000 -294 883 -290 884 -278 887 -270 889 -266 890 -261 891 -246 894 -241 895 -225 898 -219 899 -213 900 -182 905 -175 906 -168 907 -160 908 -150 909 -140 910 -128 911 -116 912 -90 914 -76 915 -39 917 -19 918 1 919 15 918 28 917 40 916 64 914 75 913 93 911 101 910 109 909 124 907 139 905 146 904...
output:
10214064.821869552562
result:
ok found '10214064.821869552', expected '10214064.821868660', error '0.000000000'
Test #24:
score: 0
Accepted
time: 6ms
memory: 4160kb
input:
777 10000 769 412 775 403 777 400 781 394 784 389 788 382 792 375 799 362 800 360 801 358 802 356 803 354 804 352 811 338 812 336 813 334 814 332 816 328 817 326 819 321 824 308 830 292 833 284 836 275 837 272 839 266 840 263 842 257 843 254 844 251 845 248 847 242 848 239 849 236 850 233 851 230 85...
output:
10499024.567478940856
result:
ok found '10499024.567478942', expected '10499024.567478029', error '0.000000000'
Test #25:
score: 0
Accepted
time: 5ms
memory: 4004kb
input:
969 10000 352 -559 348 -560 344 -561 336 -563 328 -565 310 -569 301 -571 296 -572 291 -573 281 -575 276 -576 266 -578 261 -579 256 -580 251 -581 246 -582 230 -585 219 -587 208 -589 191 -592 185 -593 179 -594 173 -595 167 -596 161 -597 154 -598 147 -599 139 -600 131 -601 123 -602 114 -603 101 -604 85...
output:
10610264.590445764069
result:
ok found '10610264.590445764', expected '10610264.590444816', error '0.000000000'
Test #26:
score: 0
Accepted
time: 5ms
memory: 3968kb
input:
1000 10000 -331 734 -328 735 -325 736 -322 737 -319 738 -313 740 -306 742 -299 744 -292 746 -288 747 -284 748 -280 749 -276 750 -268 752 -264 753 -260 754 -252 756 -248 757 -235 760 -226 762 -217 764 -212 765 -207 766 -202 767 -192 769 -187 770 -177 772 -172 773 -167 774 -156 776 -145 778 -128 781 -...
output:
10215997.705077031385
result:
ok found '10215997.705077032', expected '10215997.705076119', error '0.000000000'
Test #27:
score: 0
Accepted
time: 4ms
memory: 4140kb
input:
1000 10000 -545 159 -544 161 -543 163 -542 165 -540 169 -539 171 -537 175 -536 177 -535 179 -534 181 -533 183 -532 185 -530 189 -529 191 -526 196 -523 201 -519 207 -517 210 -515 213 -513 216 -511 219 -508 223 -504 228 -503 229 -502 230 -501 231 -500 232 -498 234 -495 237 -494 238 -493 239 -491 241 -...
output:
8089958.1991286079428
result:
ok found '8089958.199128608', expected '8089958.199127864', error '0.000000000'
Test #28:
score: -100
Wrong Answer
time: 6ms
memory: 4136kb
input:
1000 10000 -674 -603 -678 -598 -682 -593 -686 -588 -690 -583 -693 -579 -696 -575 -699 -571 -702 -567 -711 -555 -717 -547 -720 -543 -725 -536 -730 -529 -735 -522 -737 -519 -739 -516 -741 -513 -743 -510 -745 -507 -747 -504 -749 -501 -753 -495 -758 -487 -761 -482 -764 -477 -768 -470 -772 -463 -780 -449...
output:
10329432.092653931629
result:
wrong answer 1st numbers differ - expected: '10330585.4913332', found: '10329432.0926539', error = '0.0001116'