QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326881 | #7569. Lines | Hanghang | WA | 3ms | 29564kb | C++14 | 1.2kb | 2024-02-14 12:28:29 | 2024-02-14 12:28:29 |
Judging History
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'