QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#329166#1880. Nikanor Loves GamesSkyjoyWA 2ms12308kbC++143.1kb2024-02-16 14:21:372024-02-16 14:21:38

Judging History

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

  • [2024-02-16 14:21:38]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12308kb
  • [2024-02-16 14:21:37]
  • 提交

answer

#include<bits/stdc++.h>
#define I using
#define love namespace
#define Elaina std
#define ll long long
I love Elaina;
const int N=500010;
ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
namespace AyaseEli{
	struct node{
		double x,y;
		bool operator<(const node &rhs)const{return (x!=rhs.x)?x<rhs.x:y<rhs.y;}
	};
	node operator+(node a,node b){return (node){a.x+b.x,a.y+b.y};}
	node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
	double operator*(node a,node b){return a.x*b.x+b.y*a.y;}
	double cross(node a,node b){return a.x*b.y-b.x*a.y;}
	double dist(node a,node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
	bool cmp(node a,node b){
		double tmp=cross(a,b);
		if(tmp>0)return 1;
		else if(tmp==0&&dist((node){0,0},a)<dist((node){0,0},b))return 1;
		else return 0;
	}
	bool CheckIn(vector<node>&a,node b){
		if(cross(b-a[0],a[1]-a[0])>0||cross(a.back()-a[0],b-a[0])>0)return 0;
		int l=1,r=a.size()-1,pos=0;
		while(l<=r){
			int mid=(l+r)/2;
			if(cmp(b-a[0],a[mid]-a[0]))r=mid-1,pos=mid-1;
			else l=mid+1;
		}
		return cross(b-a[pos],a[(pos+1)%a.size()]-a[pos])<=0;
	}
	void ConvexHull(vector<node>a,vector<node>&b){
		sort(a.begin(),a.end());
		b.clear();
		for(int i=0;i<a.size();i++){
			while(b.size()>1&&cross(b[b.size()-2]-b.back(),a[i]-b.back())>=0)b.pop_back();
			b.push_back(a[i]);
		}
		int lim=b.size();
		for(int i=a.size()-2;i>=0;i--){
			while(b.size()>lim&&cross(b[b.size()-2]-b.back(),a[i]-b.back())>=0)b.pop_back();
			b.push_back(a[i]);
		}
		b.pop_back();
	}
	void Minkowski(vector<node>&a,vector<node>&b,vector<node>&c){
		if(a.empty()||b.empty()){
			if(a.empty())c=b;
			if(b.empty())c=a;
			return;
		}
		c.clear();
		int i=0,j=0;
		node cur=a[0]+b[0],t1,t2;
		c.push_back(cur);
		while(i<a.size()&&j<b.size()){
			t1=(i<a.size()-1)?a[i+1]-a[i]:a[0]-a[i],t2=(j!=b.size()-1)?b[j+1]-b[j]:b[0]-b[j];
			if(cross(t1,t2)>0||(cross(t1,t2)==0&&t1*t2>0))cur=cur+t1,i++;
			else cur=cur+t2,j++;
			c.push_back(cur);
		}
		while(i<a.size()){
			cur=cur+((i!=a.size()-1)?a[i+1]-a[i]:a[0]-a[i]),i++;
			c.push_back(cur);
		}
		while(j<b.size()){
			cur=cur+((j!=b.size()-1)?b[j+1]-b[j]:b[0]-b[j]),j++;
			c.push_back(cur);
		}
		ConvexHull(c,c);
	}
}
I love AyaseEli;
ll n,a[N],b[N],x[N],pos[N<<1],sum[N<<1],m;
double ans=-1e18;
vector<node>A;
int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=pos[2*i-1]=read(),b[i]=pos[2*i]=read(),x[i]=read();
	pos[2*n+1]=1;
	sort(pos+1,pos+2*n+2);
	m=unique(pos+1,pos+2*n+2)-pos-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(pos+1,pos+m+1,a[i])-pos,b[i]=lower_bound(pos+1,pos+m+1,b[i])-pos;
		sum[a[i]]+=2*x[i],sum[b[i]]+=2*x[i],sum[0]-=2*x[i];
	}
	for(int i=1;i<=m;i++){
		sum[i]+=sum[i-1];
		A.push_back((node){pos[i],sum[i]});
	}
	ConvexHull(A,A);
	for(int i=0,j=A.size()-1;i<A.size();i++){
		while(j&&A[j].y-4ll*A[i].x*A[j].x<=A[j-1].y-4ll*A[i].x*A[j-1].x)j--;
		ans=max(ans,A[i].y+A[j].y-4ll*A[i].x*A[j].x);
	}
	printf("%lf",ans/4);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 12164kb

input:

2
1 4 15
3 5 10

output:

2.500000

result:

ok found '2.5000000', expected '2.5000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 12068kb

input:

1
2 2 8

output:

4.000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 12308kb

input:

3
94 68 49
51 2 63
26 85 20

output:

-94.000000

result:

wrong answer 1st numbers differ - expected: '-73.0000000', found: '-94.0000000', error = '0.2876712'