QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#324625 | #8214. Huge Oil Platform | ucup-team052 | WA | 1ms | 3904kb | C++23 | 4.3kb | 2024-02-10 22:03:54 | 2024-02-10 22:03:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 405
const double eps=1e-10;
int sgn(double x)
{
if(x<-eps) return -1;
else if(x>eps) return 1;
else return 0;
}
struct Vec
{
double x,y;
Vec(double a=0,double b=0) {x=a,y=b;}
double norm() {return x*x+y*y;}
double abs() {return sqrt(x*x+y*y);}
};
Vec rdvec()
{
double x,y;
scanf("%lf %lf",&x,&y);
return Vec(x,y);
}
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (const Vec &x,const double y) {return Vec(x.x*y,x.y*y);}
Vec operator / (const Vec &x,const double y) {return Vec(x.x/y,x.y/y);}
// double dis(const Vec &x,const Vec &y) {return (x-y).abs();}
void print(Vec x) {printf("%.10lf %.10lf\n",x.x,x.y);}
double cdot(const Vec &x,const Vec &y) {return x.x*y.x+x.y*y.y;}
double cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
int ccw(Vec x,Vec y,Vec z)
{
int w=sgn(cross(y-x,z-x));
if(w==1) return 1; // ccw
else if(w==-1) return -1; // cw;
else return 0; // coline
}
struct Seg
{
Vec s,t; // two points
Seg(Vec x,Vec y) {s=x,t=y;}
Seg() {}
Vec d() {return t-s;}
Vec point(double p) {return s+(t-s)*p;}
};
int parallel(Seg p,Seg q) {return sgn(cross(p.d(),q.d()))==0;}
Vec proj(Seg l,Vec x)
{
double p=cdot(l.t-l.s,x-l.s)/(l.t-l.s).norm();
return l.point(p);
}
Vec a[N]; int w[N];
int n,id[N],tid[N],rev[N],m;
double ans,dis[N],pos[N];
struct SMT
{
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)/2)
double tag1[N*4],tag2[N*4],ans[N*4],mx[N*4],mn[N*4];
void pushup(int u)
{
ans[u]=max(ans[ls],ans[rs]);
mx[u]=max(mx[ls],mx[rs]);
mn[u]=min(mn[ls],mn[rs]);
ans[u]=max(ans[u],mx[rs]-mn[ls]);
}
void build(int u,int l,int r)
{
tag1[u]=tag2[u]=0;
if(l==r)
{
tag1[u]=tag2[u]=-2*pos[tid[l]];
mx[u]=tag1[u],mn[u]=tag2[u];
ans[u]=0;
return ;
}
build(ls,l,mid),build(rs,mid+1,r);
pushup(u);
}
void pushdown(int u)
{
tag1[ls]+=tag1[u],tag2[ls]+=tag2[u],mx[ls]+=tag1[u],mn[ls]+=tag2[u];
tag1[rs]+=tag1[u],tag2[rs]+=tag2[u],mx[rs]+=tag1[u],mn[rs]+=tag2[u];
tag1[u]=tag2[u]=0;
}
void update1(int u,int l,int r,int L,int R,double w)
{
if(L>R) return ;
if(L<=l&&r<=R)
{
tag1[u]+=w,mx[u]+=w;
return ;
}
pushdown(u);
if(mid>=L) update1(ls,l,mid,L,R,w);
if(mid<R) update1(rs,mid+1,r,L,R,w);
pushup(u);
}
void update2(int u,int l,int r,int L,int R,double w)
{
if(L>R) return ;
if(L<=l&&r<=R)
{
tag2[u]+=w,mn[u]+=w;
return ;
}
pushdown(u);
if(mid>=L) update2(ls,l,mid,L,R,w);
if(mid<R) update2(rs,mid+1,r,L,R,w);
pushup(u);
}
double query() {return ans[1];}
}smt;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),w[i]=read();
for(int i=1;i<=n;i++) if(w[i]>ans) ans=w[i];
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
{
if(i==j) continue;
// printf("Solving %d %d\n",i,j);
Seg tmps(a[i],a[j]);
m=0; Vec zero=proj(tmps,Vec(0,0));
for(int k=1;k<=n;k++)
{
if(ccw(a[j],a[k],a[i])==-1) continue;
id[++m]=k; tid[m]=k;
Vec cv=proj(tmps,a[k]);
pos[k]=(cv-zero).abs();
dis[k]=(cv-a[k]).abs();
// printf("%d : %lf %lf\n",k,dis[k],pos[k]);
}
sort(tid+1,tid+m+1,[&](int x,int y){return pos[x]<pos[y];});
sort(id+1,id+m+1,[&](int x,int y){return dis[x]<dis[y];});
for(int k=1;k<=m;k++) rev[tid[k]]=k;
smt.build(1,1,m);
double res=0;
for(int k=1;k<=m;k++)
{
int u=id[k];
smt.update1(1,1,m,rev[u],m,w[u]);
smt.update2(1,1,m,rev[u]+1,m,w[u]);
res=max(res,smt.query()-2*dis[u]);
// printf("add u - %lf\n",smt.query()-2*dis[u]);
}
ans=max(ans,res);
}
printf("%.8lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
input:
2 1 1 1 3 3 1
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 4 5 5 4 6 7 1 3 8
output:
10.10050506
result:
ok found '10.1005051', expected '10.1005051', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
2 0 0 1 1000000 1000000 1000000000
output:
1000000000.00000000
result:
ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3904kb
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:
6315.61113734
result:
wrong answer 1st numbers differ - expected: '6092.4427126', found: '6315.6111373', error = '0.0366304'