QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#338617 | #8214. Huge Oil Platform | ucup-team134 | WA | 0ms | 3924kb | C++17 | 3.9kb | 2024-02-26 04:30:30 | 2024-02-26 04:30:31 |
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;
vector<int> ids;
vector<ldb> len;
pt a[N];
int w[N],idx[N];
const int M=4*N;
ldb mx[2][M],lzy[2][M];
void upd(int t,int c,ldb x){
mx[t][c]+=x;
lzy[t][c]+=x;
}
void pull(int t,int c){
mx[t][c]=max(mx[t][c<<1],mx[t][c<<1|1])+lzy[t][c];
}
void Build(int t,int c,int ss,int se){
lzy[t][c]=0;
if(ss==se){
mx[t][c]=t==0?-2*len[ss-1]:2*len[ss-1];
return;
}
int mid=ss+se>>1;
Build(t,c<<1,ss,mid);
Build(t,c<<1|1,mid+1,se);
pull(t,c);
}
void Add(int t,int c,int ss,int se,int qs,int qe,ldb x){
if(qs>qe||qs>se||ss>qe)return;
if(qs<=ss&&qe>=se){
upd(t,c,x);
return;
}
int mid=ss+se>>1;
Add(t,c<<1,ss,mid,qs,qe,x);
Add(t,c<<1|1,mid+1,se,qs,qe,x);
pull(t,c);
}
ldb Get(int t,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[t][c];
int mid=ss+se>>1;
return max(Get(t,c<<1,ss,mid,qs,qe),Get(t,c<<1|1,mid+1,se,qs,qe))+lzy[t][c];
}
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;
ids.clear();
line l(a[i],a[j]);
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]);});
len.clear();
for(int k=0;k<ids.size();k++){
idx[ids[k]]=k+1;
len.pb(proj_len(l,a[ids[k]]));
}
int m=ids.size();
Build(0,1,1,m);
Build(1,1,1,m);
/*for(int k:ids){
Build(0,1,1,m);
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(0,1,1,m,idx[k],m,w[k]);
Add(1,1,1,m,idx[k]+1,m,-w[k]);
ldb now=-2*dist(l,a[k])+mx[0][1]+mx[1][1];//Get(0,1,1,m,R,m)+Get(1,1,1,m,1,L);
ans=max(ans,now);
//printf("%i %i %i %lf\n",i,j,k,now);
}
}
}
printf("%.12lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3924kb
input:
2 1 1 1 3 3 1
output:
5.656854249492
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '5.6568542', error = '4.6568542'