QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326881#7569. LinesHanghangWA 3ms29564kbC++141.2kb2024-02-14 12:28:292024-02-14 12:28:29

Judging History

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

  • [2024-02-14 12:28:29]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:29564kb
  • [2024-02-14 12:28:29]
  • 提交

answer

//test
#include<bits/stdc++.h>
using namespace std;
int n;
#define ll long long
struct TB{
	ll x[300100],y[301000];int top;
	inline void ins(ll a,ll b){
		while(top>1&&(y[top]-y[top-1])*(a-x[top])<=(b-y[top])*(x[top]-x[top-1]))top--;
		x[++top]=a,y[top]=b;
	}
}P[3],ANS;
ll fx[1010000],fy[1010000],M;
TB operator + (const TB &a,const TB &b){
	TB c;
	int O=1;
	fx[1]=a.x[1]+b.x[1],fy[1]=a.y[1]+b.y[1];
	int i=1,j=1;
	while(i<a.top&&j<b.top){
		if((a.y[i+1]-a.y[i])*(b.x[j+1]-b.x[j])>=(b.y[j+1]-b.y[j])*(a.x[i+1]-a.x[i]))i++;
		else j++;
		O++,fx[O]=a.x[i]+b.x[j],fy[O]=a.y[i]+b.y[j];
	}
	while(i<a.top)i++,O++,fx[O]=a.x[i]+b.x[j],fy[O]=a.y[i]+b.y[j];
	while(j<b.top)j++,O++,fx[O]=a.x[i]+b.x[j],fy[O]=a.y[i]+b.y[j];
	c.top=O;
	for(int i=1;i<=O;i++)c.x[i]=fx[i],c.y[i]=fy[i];
	//c.top=0;
	//for(int i=1;i<=O;i++)c.ins(fx[i],fy[i]);
	return c;
}
bool vis[1001000];
int main(){
	//诈骗题,考虑
	scanf("%d",&n);
	for(int o=0;o<3;o++)
	for(int i=0,a;i<=n;i++)scanf("%d",&a),P[o].ins(i,a);
	ANS=P[0]+P[1]+P[2];
	for(int i=1;i<=ANS.top;i++)vis[ANS.x[i]]=1;
	int ans=0;
	for(int i=0;i<=n*3;i++)if(!vis[i])ans++;
	printf("%d\n",ans);
	for(int i=0;i<=n*3;i++)if(!vis[i])printf("%d ",i);
	//求闵和的上凸包
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 29564kb

input:

3
3 1 8 7
9 1 3 1
5 1 1 6

output:

5
1 3 4 7 8 

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 25312kb

input:

1
1 2
1 2
1 2

output:

0

result:

wrong answer 1st numbers differ - expected: '2', found: '0'