QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#338617#8214. Huge Oil Platformucup-team134WA 0ms3924kbC++173.9kb2024-02-26 04:30:302024-02-26 04:30:31

Judging History

你现在查看的是最新测评结果

  • [2024-02-26 04:30:31]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3924kb
  • [2024-02-26 04:30:30]
  • 提交

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'