QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#338611 | #8214. Huge Oil Platform | ucup-team134 | TL | 1ms | 4084kb | C++17 | 3.7kb | 2024-02-26 04:11:24 | 2024-02-26 04:11:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ldb double
#define mp make_pair
#define pb push_back
// 2D Point
struct pt{
ll x,y;
pt():x(0),y(0){}
pt(ll a,ll b):x(a),y(b){}
};
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator * (pt a,ll b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,ll b){return pt(a.x/b,a.y/b);}
bool operator < (pt a,pt b){return mp(a.x,a.y)<mp(b.x,b.y);}
ll dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
ll cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
ldb abs(pt a){return sqrt(dot(a,a));}
ldb angle(pt a){return atan2(a.y,a.x);}
pt perp(pt a){return pt(-a.y,a.x);}
int part(pt a){return a.y>0||(a.y==0&&a.x>0)?0:1;}
bool cmp(pt a,pt b){return mp(part(a),(ll)0)<mp(part(b),cross(a,b));}
// 2D Line
struct line{
pt v;
ll c;
line(pt a,pt b){
v=b-a;
c=cross(v,a);
}
};
ll side(line a,pt b){return cross(a.v,b)-a.c;}
ldb dist(line a,pt b){return side(a,b)/abs(a.v);}
ldb proj_len(line a,pt b){return dot(a.v,b)/abs(a.v);}
pt project(line a,pt b){return b+perp(a.v)*dist(a,b);}
pt reflect(line a,pt b){return b+perp(a.v)*2*dist(a,b);}
struct pt2{
ldb x,y;
pt2():x(0),y(0){}
pt2(pt a):x(a.x),y(a.y){}
pt2(ldb a,ldb b):x(a),y(b){}
};
pt2 operator / (pt2 a,ldb b){return pt2(a.x/b,a.y/b);}
pt2 rotate(pt a,ldb ang){
ldb c=cos(ang);
ldb s=sin(ang);
return pt2(a.x*c-a.y*s,a.x*s+a.y*c);
}
pt2 inter(line a,line b){
return pt2(a.v*b.c-b.v*a.c)/cross(a.v,b.v);
}
// 2D Segment
struct segment{
pt a,b;
segment(pt c,pt d):a(c),b(d){}
};
//...
// Circle
struct circle{
pt O;
ll r;
circle(pt a,ll b):O(a),r(b){}
};
//...
// 3D...
// Sphere...
const ldb inf=1e18;
const int N=405;
const int M=4*N;
int ls[M],rs[M],tsz,root[2];
ldb mx[M],lzy[M];
void upd(int c,ldb x){
mx[c]+=x;
lzy[c]+=x;
}
void pull(int c){
mx[c]=max(mx[ls[c]],mx[rs[c]])+lzy[c];
}
void Add(int&c,int ss,int se,int qs,int qe,ldb x){
if(qs>qe||qs>se||ss>qe)return;
if(!c)c=++tsz;
if(qs<=ss&&qe>=se){
upd(c,x);
return;
}
int mid=ss+se>>1;
Add(ls[c],ss,mid,qs,qe,x);
Add(rs[c],mid+1,se,qs,qe,x);
pull(c);
}
ldb Get(int c,int ss,int se,int qs,int qe){
if(qs>qe||qs>se||ss>qe)return -inf;
if(qs<=ss&&qe>=se)return mx[c];
int mid=ss+se>>1;
return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe))+lzy[c];
}
void Clear(){
for(int i=1;i<=tsz;i++){
ls[i]=rs[i]=0;
mx[i]=lzy[i]=0;
}
root[0]=root[1]=tsz=0;
}
pt a[N];
int w[N],idx[N];
int main(){
int n;
scanf("%i",&n);
for(int i=1;i<=n;i++){
scanf("%lld %lld %i",&a[i].x,&a[i].y,&w[i]);
}
ldb ans=-inf;
for(int i=1;i<=n;i++)ans=max(ans,(ldb)w[i]);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
line l(a[i],a[j]);
vector<int> ids;
for(int k=1;k<=n;k++){
if(side(l,a[k])>=0){
ids.pb(k);
}
}
sort(ids.begin(),ids.end(),[&](int i,int j){return dot(l.v,a[i])<dot(l.v,a[j]);});
for(int k=0;k<ids.size();k++)idx[ids[k]]=k+1;
int m=ids.size();
for(int k:ids){
Add(root[0],1,m,idx[k],idx[k],-proj_len(l,a[k])*2);
Add(root[1],1,m,idx[k],idx[k],+proj_len(l,a[k])*2);
}
sort(ids.begin(),ids.end(),[&](int i,int j){return side(l,a[i])<side(l,a[j]);});
for(int k:ids){
Add(root[0],1,m,idx[k],m,w[k]);
Add(root[1],1,m,idx[k]+1,m,-w[k]);
int L=min({idx[i],idx[j],idx[k]});
int R=max({idx[i],idx[j],idx[k]});
ldb now=-2*dist(l,a[k])+Get(root[0],1,m,R,m)+Get(root[1],1,m,1,L);
ans=max(ans,now);
//printf("%i %i %i %lf\n",i,j,k,now);
}
Clear();
}
}
printf("%.12lf\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3888kb
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: 3888kb
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: 3844kb
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: 3872kb
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: 4084kb
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.257312827458
result:
ok found '11878.2573128', expected '11878.2573128', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3840kb
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: 1ms
memory: 4032kb
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.595617883408
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...