QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#344602 | #8214. Huge Oil Platform | SolitaryDream# | TL | 1ms | 4080kb | C++17 | 2.3kb | 2024-03-04 20:18:55 | 2024-03-04 20:18:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef long double db;
typedef long long ll;
struct Point {
ll x,y;
Point operator -(const Point &s) const{
return {x-s.x,y-s.y};
}
db Len() const{
return hypot(x,y);
}
};
ll det(Point a,Point b) {
return a.x*b.y-a.y*b.x;
}
ll dot(Point a,Point b) {
return a.x*b.x+a.y*b.y;
}
const int N=405;
Point a[N];
int w[N];
vector<db> X;
struct node {
db ans,lmx,rmx,sum;
} T[N<<2];
#define ls p<<1
#define rs p<<1|1
#define lson L,mid,ls
#define rson mid+1,R,rs
void build(int L,int R,int p) {
T[p]={0,0,0,-(X[R]-X[L])*2};
if(L==R) return ;
int mid=L+R>>1;
build(lson);
build(rson);
}
void Insert(int L,int R,int p,int x,int v) {
if(L==R) {
T[p].ans+=v;
T[p].lmx+=v;
T[p].rmx+=v;
T[p].sum+=v;
return ;
}
int mid=L+R>>1;
if(x<=mid) Insert(lson,x,v);
else Insert(rson,x,v);
db d=(X[mid+1]-X[mid])*2;
T[p].ans=max({T[ls].ans,T[rs].ans,T[ls].rmx+T[rs].lmx-d});
T[p].lmx=max(T[ls].lmx,T[ls].sum+T[rs].lmx-d);
T[p].rmx=max(T[rs].rmx,T[rs].sum+T[ls].rmx-d);
T[p].sum=T[ls].sum+T[rs].sum-d;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(12);
int n;
cin >> n;
db res=0;
FOR(i,1,n) {
int x,y;
cin >> x >> y >> w[i];
a[i]={x,y};
res=max(res,(db)w[i]);
}
FOR(i,1,n) FOR(j,1,n) if(i!=j) {
vector<tuple<db,db,int>> vec;
X.clear();
FOR(k,1,n) if(det(a[j]-a[i],a[k]-a[i])>=0) {
db y=det(a[j]-a[i],a[k]-a[i])/(a[j]-a[i]).Len();
db x=dot(a[j]-a[i],a[k]-a[i])/(a[j]-a[i]).Len();
X.push_back(x);
vec.push_back({y,x,w[k]});
}
sort(X.begin(),X.end());
X.erase(unique(X.begin(),X.end()),X.end());
sort(vec.begin(),vec.end());
build(0,X.size()-1,1);
for(auto [y,x,v]: vec) {
int p=lower_bound(X.begin(),X.end(),x)-X.begin();
// cerr << i << ' ' << j << ' ' << v << endl;
Insert(0,X.size()-1,1,p,v);
res=max(res,T[1].ans-y*2);
}
}
cout << res << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4008kb
input:
2 1 1 1 3 3 1
output:
1.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
3 4 5 5 4 6 7 1 3 8
output:
10.100505063388
result:
ok found '10.1005051', expected '10.1005051', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
2 0 0 1 1000000 1000000 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
20 328 207 21 365 145 188 347 79 41 374 335 699 288 250 97 32 267 131 296 332 434 2 91 36 139 43 21 26 455 696 57 135 410 14 500 396 255 181 646 103 114 593 309 351 787 207 316 138 440 416 806 413 349 695 413 201 501 455 396 442
output:
6092.442712623783
result:
ok found '6092.4427126', expected '6092.4427126', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
20 38 207 766 202 485 964 257 466 900 205 486 738 166 53 716 61 94 881 252 165 182 63 292 612 225 278 242 224 242 566 381 196 702 56 494 997 268 288 884 379 227 3 357 271 975 55 73 678 260 55 623 399 369 515 116 354 580 404 239 950
output:
11878.257312827460
result:
ok found '11878.2573128', expected '11878.2573128', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
20 249 215 320 38 48 229 457 366 56 36 142 186 44 96 935 97 190 143 215 218 123 116 486 291 304 232 463 429 297 29 479 475 97 97 198 405 69 395 121 381 121 926 137 197 972 410 91 218 87 421 737 117 390 144 319 287 170 353 302 754
output:
5573.255896932630
result:
ok found '5573.2558969', expected '5573.2558969', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
20 474 215 66 376 120 6 367 259 211 362 293 34 416 407 554 133 292 894 171 278 871 459 187 674 383 192 980 352 78 899 83 27 684 138 185 709 357 234 359 390 241 40 418 124 161 258 348 462 408 59 851 110 184 668 28 447 761 20 131 367
output:
8510.595617883409
result:
ok found '8510.5956179', expected '8510.5956179', error '0.0000000'
Test #8:
score: -100
Time Limit Exceeded
input:
400 979422 264252 76260 922920 334464 58710 87057 798078 39652 602478 649867 49073 388746 161788 44501 727471 373113 28061 944959 505744 22145 191465 164645 49421 102241 771049 65953 44911 762286 34082 112779 537040 98117 688054 585935 53647 391845 931395 55355 788464 698271 91449 984533 409449 8331...