3 条题解

  • 0
    @ 2023-10-10 13:22:41

    #include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; const int maxn=5E5+5; const int base=33333; const ld eps=1E-10; const ld inf=1E17; int n,m,T; ll a[maxn],b[maxn],ans[maxn]; int idR[maxn],idL[maxn]; ld rightPlane[maxn],leftPlane[maxn]; int q[maxn]; struct pt { double x,y; pt(double a=0,double b=0):x(a),y(b){} pt operator+(const pt&A){return pt(x+A.x,y+A.y);} pt operator-(const pt&A){return pt(x-A.x,y-A.y);} pt operator*(ld d){return pt(xd,yd);} double operator*(const pt&A){return xA.y-yA.x;} void out(){cout<<"("<<x<<","<<y<<")"<<endl;} }; struct line { pt A,B; int id,b; int slope; line(){} line(pt a,pt b):A(a),B(b){} }s[maxn]; inline ll max(ll x,ll y) { return x>y?x:y; } inline ll min(ll x,ll y) { return x<y?x:y; } inline ll get(ll x,ll a,ll b) { return (ax+b)x; } inline int read() { bool flag=0; char ch=getchar(); if(ch=='-') flag^=1; while(!isdigit(ch)) { ch=getchar(); if(ch=='-') flag^=1; } int sum=ch-'0'; ch=getchar(); while(isdigit(ch)) { sum=sum10+ch-'0'; ch=getchar(); } return flag?-sum:sum; } void write(ll x) { if(x>=10) write(x/10); putchar('0'+x%10); } inline void writen(ll x) { if(x<0) { putchar('-'); write(-x); } else write(x); putchar('\n'); } inline int cross(pt A,pt B) { ld d=AB; if(abs(d)<=eps) return 0; return d>0?1:-1; } inline pt intersection(line a,line b) { pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A; if(cross(A,B)0) return pt(inf,inf); ld d=-(BC)/(BA); return b.A+A*d; } inline int onClockwise(line a,line b,line c) { return cross(a.B-a.A,intersection(b,c)-a.A)-1; } bool cmpR(line A,line B) { if(A.slopeB.slope) return A.b<B.b; return A.slope<B.slope; } bool cmpL(line A,line B) { if(A.slopeB.slope) return A.b>B.b; return A.slope<B.slope; } void initR() { sort(s+1,s+n+1,cmpR); int L=1,R=0; for(int i=1;i<=n;++i) { while(i!=n&&s[i].slopes[i+1].slope) ++i; while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]])) --R; q[++R]=i; } for(int i=1;i<=R;++i) idR[i]=s[q[i]].id; for(int i=1;i<R;++i) rightPlane[i]=intersection(s[q[i]],s[q[i+1]]).x; int pos=1; for(int i=-base;i<=base;++i) { while(pos<R&&rightPlane[pos]<ld(i)) ++pos; ans[i+base]=get(i,s[q[pos]].slope,s[q[pos]].b); } } void initL() { sort(s+1,s+n+1,cmpL); int L=1,R=0; for(int i=1;i<=n;++i) { while(i!=n&&s[i].slopes[i+1].slope) ++i; while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]])) --R; q[++R]=i; } for(int i=1;i<=R;++i) idL[i]=s[q[i]].id; for(int i=1;i<R;++i) leftPlane[i]=intersection(s[q[i]],s[q[i+1]]).x; int pos=1; for(int i=base;i>=-base;--i) { while(pos<R&&ld(i)<leftPlane[pos]) ++pos; ans[i+base]=max(ans[i+base],get(i,s[q[pos]].slope,s[q[pos]].b)); } } int main() { // freopen("A.in","r",stdin); // freopen("A.out","w",stdout); ios::sync_with_stdio(false); n=read(),T=read(); for(int i=1;i<=n;++i) { a[i]=read(),b[i]=read(); s[i].A=pt(0,b[i]); s[i].B=pt(1,a[i]+b[i]); s[i].slope=a[i]; s[i].b=b[i]; s[i].id=i; } initR(); for(int i=1;i<=n;++i) swap(s[i].A,s[i].B); initL(); while(T--) { int x=read(); writen(ans[x+base]); } return 0; }

    • 0
      @ 2023-3-25 17:46:09 
      #include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
const int maxn=5E5+5;
const int base=33333;
const ld eps=1E-10;
const ld inf=1E17;
int n,m,T;
ll a[maxn],b[maxn],ans[maxn];
int idR[maxn],idL[maxn];
ld rightPlane[maxn],leftPlane[maxn];
int q[maxn];
struct pt
{
double x,y;
pt(double a=0,double b=0):x(a),y(b){}
pt operator+(const pt&A){return pt(x+A.x,y+A.y);}
pt operator-(const pt&A){return pt(x-A.x,y-A.y);}
pt operator*(ld d){return pt(x*d,y*d);}
double operator*(const pt&A){return x*A.y-y*A.x;}
void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
struct line
{
pt A,B;
int id,b;
int slope;
line(){}
line(pt a,pt b):A(a),B(b){}
}s[maxn];
inline ll max(ll x,ll y)
{
return x>y?x:y;
}
inline ll min(ll x,ll y)
{
return x<y?x:y;
}
inline ll get(ll x,ll a,ll b)
{
return (a*x+b)*x;
}
inline int read()
{
bool flag=0;
char ch=getchar();
if(ch=='-')
flag^=1;
while(!isdigit(ch))
{
ch=getchar();
if(ch=='-')
flag^=1;
}
int sum=ch-'0';
ch=getchar();
while(isdigit(ch))
{
sum=sum*10+ch-'0';
ch=getchar();
}
return flag?-sum:sum;
}
void write(ll x)
{
if(x>=10)
write(x/10);
putchar('0'+x%10);
}
inline void writen(ll x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
write(x);
putchar('\n');
}
inline int cross(pt A,pt B)
{
ld d=A*B;
if(abs(d)<=eps)
return 0;
return d>0?1:-1;
}
inline pt intersection(line a,line b)
{
pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A;
if(cross(A,B)==0)
return pt(inf,inf);
ld d=-(B*C)/(B*A);
return b.A+A*d;
}
inline int onClockwise(line a,line b,line c)
{
return cross(a.B-a.A,intersection(b,c)-a.A)==-1;
}
bool cmpR(line A,line B)
{
if(A.slope==B.slope)
return A.b<B.b;
return A.slope<B.slope;
}
bool cmpL(line A,line B)
{
if(A.slope==B.slope)
return A.b>B.b;
return A.slope<B.slope;
}
void initR()
{
sort(s+1,s+n+1,cmpR);
int L=1,R=0;
for(int i=1;i<=n;++i)
{
while(i!=n&&s[i].slope==s[i+1].slope)
++i;
while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]]))
--R;
q[++R]=i;
}
for(int i=1;i<=R;++i)
idR[i]=s[q[i]].id;
for(int i=1;i<R;++i)
rightPlane[i]=intersection(s[q[i]],s[q[i+1]]).x;
int pos=1;
for(int i=-base;i<=base;++i)
{
while(pos<R&&rightPlane[pos]<ld(i))
++pos;
ans[i+base]=get(i,s[q[pos]].slope,s[q[pos]].b);
}
}
void initL()
{
sort(s+1,s+n+1,cmpL);
int L=1,R=0;
for(int i=1;i<=n;++i)
{
while(i!=n&&s[i].slope==s[i+1].slope)
++i;
while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]]))
--R;
q[++R]=i;
}
for(int i=1;i<=R;++i)
idL[i]=s[q[i]].id;
for(int i=1;i<R;++i)
leftPlane[i]=intersection(s[q[i]],s[q[i+1]]).x;
int pos=1;
for(int i=base;i>=-base;--i)
{
while(pos<R&&ld(i)<leftPlane[pos])
++pos;
ans[i+base]=max(ans[i+base],get(i,s[q[pos]].slope,s[q[pos]].b));
}
}
int main()
{
//    freopen("A.in","r",stdin);
//    freopen("A.out","w",stdout);
ios::sync_with_stdio(false);
n=read(),T=read();
for(int i=1;i<=n;++i)
{
a[i]=read(),b[i]=read();
s[i].A=pt(0,b[i]);
s[i].B=pt(1,a[i]+b[i]);
s[i].slope=a[i];
s[i].b=b[i];
s[i].id=i;
}
initR();
for(int i=1;i<=n;++i)
swap(s[i].A,s[i].B);
initL();
while(T--)
{
int x=read();
writen(ans[x+base]);
}
return 0;
}
      • 0
        @ 2022-5-24 16:10:54

        首先将xx大于00还是小于00分类，对于某一类全都除以xx，那么就得到了一些直线。最优的答案一定在某条最上方或最下方的直线上，半平面交或凸包维护即可。

        #include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
const int maxn=5E5+5;
const int base=33333;
const ld eps=1E-10;
const ld inf=1E17;
int n,m,T;
ll a[maxn],b[maxn],ans[maxn];
int idR[maxn],idL[maxn];
ld rightPlane[maxn],leftPlane[maxn];
int q[maxn];
struct pt
{
double x,y;
pt(double a=0,double b=0):x(a),y(b){}
pt operator+(const pt&A){return pt(x+A.x,y+A.y);}
pt operator-(const pt&A){return pt(x-A.x,y-A.y);}
pt operator*(ld d){return pt(x*d,y*d);}
double operator*(const pt&A){return x*A.y-y*A.x;}
void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
struct line
{
pt A,B;
int id,b;
int slope;
line(){}
line(pt a,pt b):A(a),B(b){}
}s[maxn];
inline ll max(ll x,ll y)
{
return x>y?x:y;
}
inline ll min(ll x,ll y)
{
return x<y?x:y;
}
inline ll get(ll x,ll a,ll b)
{
return (a*x+b)*x;
}
inline int read()
{
bool flag=0;
char ch=getchar();
if(ch=='-')
flag^=1;
while(!isdigit(ch))
{
ch=getchar();
if(ch=='-')
flag^=1;
}
int sum=ch-'0';
ch=getchar();
while(isdigit(ch))
{
sum=sum*10+ch-'0';
ch=getchar();
}
return flag?-sum:sum;
}
void write(ll x)
{
if(x>=10)
write(x/10);
putchar('0'+x%10);
}
inline void writen(ll x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
write(x);
putchar('\n');
}
inline int cross(pt A,pt B)
{
ld d=A*B;
if(abs(d)<=eps)
return 0;
return d>0?1:-1;
}
inline pt intersection(line a,line b)
{
pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A;
if(cross(A,B)==0)
return pt(inf,inf);
ld d=-(B*C)/(B*A);
return b.A+A*d;
}
inline int onClockwise(line a,line b,line c)
{
return cross(a.B-a.A,intersection(b,c)-a.A)==-1;
}
bool cmpR(line A,line B)
{
if(A.slope==B.slope)
return A.b<B.b;
return A.slope<B.slope;
}
bool cmpL(line A,line B)
{
if(A.slope==B.slope)
return A.b>B.b;
return A.slope<B.slope;
}
void initR()
{
sort(s+1,s+n+1,cmpR);
int L=1,R=0;
for(int i=1;i<=n;++i)
{
while(i!=n&&s[i].slope==s[i+1].slope)
++i;
while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]]))
--R;
q[++R]=i;
}
for(int i=1;i<=R;++i)
idR[i]=s[q[i]].id;
for(int i=1;i<R;++i)
rightPlane[i]=intersection(s[q[i]],s[q[i+1]]).x;
int pos=1;
for(int i=-base;i<=base;++i)
{
while(pos<R&&rightPlane[pos]<ld(i))
++pos;
ans[i+base]=get(i,s[q[pos]].slope,s[q[pos]].b);
}
}
void initL()
{
sort(s+1,s+n+1,cmpL);
int L=1,R=0;
for(int i=1;i<=n;++i)
{
while(i!=n&&s[i].slope==s[i+1].slope)
++i;
while(R-1>=L&&onClockwise(s[i],s[q[R]],s[q[R-1]]))
--R;
q[++R]=i;
}
for(int i=1;i<=R;++i)
idL[i]=s[q[i]].id;
for(int i=1;i<R;++i)
leftPlane[i]=intersection(s[q[i]],s[q[i+1]]).x;
int pos=1;
for(int i=base;i>=-base;--i)
{
while(pos<R&&ld(i)<leftPlane[pos])
++pos;
ans[i+base]=max(ans[i+base],get(i,s[q[pos]].slope,s[q[pos]].b));
}
}
int main()
{
//    freopen("A.in","r",stdin);
//    freopen("A.out","w",stdout);
ios::sync_with_stdio(false);
n=read(),T=read();
for(int i=1;i<=n;++i)
{
a[i]=read(),b[i]=read();
s[i].A=pt(0,b[i]);
s[i].B=pt(1,a[i]+b[i]);
s[i].slope=a[i];
s[i].b=b[i];
s[i].id=i;
}
initR();
for(int i=1;i<=n;++i)
swap(s[i].A,s[i].B);
initL();
while(T--)
{
int x=read();
writen(ans[x+base]);
}
return 0;
}
        • 1

        Quadratic Function

        信息

        ID
        54
        时间
        1000ms
        内存
        256MiB
        难度
        5
        标签
        (无)
        递交数
        138
        已通过
        43
        上传者
        1. 关于
        2. 联系我们
        3. 隐私
        4. 服务条款
        5. 版权申诉
        6. Language
        7. 兼容模式
        8. 主题
        2. © 2021-2024 Hydro.ac
        4. Worker 0 in 105ms
        5. Hydro v4.18.2 Professional