QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#324625#8214. Huge Oil Platformucup-team052WA 1ms3904kbC++234.3kb2024-02-10 22:03:542024-02-10 22:03:55

Judging History

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

  • [2024-02-10 22:03:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3904kb
  • [2024-02-10 22:03:54]
  • 提交

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'