QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#338611#8214. Huge Oil Platformucup-team134TL 1ms4084kbC++173.7kb2024-02-26 04:11:242024-02-26 04:11:24

Judging History

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

  • [2024-02-26 04:11:24]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4084kb
  • [2024-02-26 04:11:24]
  • 提交

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...

output:


result: