BZOJ3941 : [Usaco2015 Feb]Fencing the Herd
The Feb
2023-09-11 14:15:04 时间
若所有点同侧则表明将各个点带入直线解析式ax+by-c后得到的值均同号
等价于最大值和最小值同号
考虑CDQ分治,每一步分治的过程中求出上下凸壳,然后三分答案即可
时间复杂度$O(n\log^2n)$
#include<cstdio> #include<algorithm> typedef long long ll; const int N=200010; const ll inf=1LL<<60; struct P{int x,y;P(){}P(int _x,int _y){x=_x,y=_y;}}b[N],q1[N],q2[N],now; struct Q{int a,b,q;ll c;Q(){}Q(int _a,int _b,ll _c,int _q){a=_a,b=_b,c=_c,q=_q;}}a[N]; int n,m,i,op,A,B,cnt,t1,t2,m1,m2,len;ll C,s1,s2,ans1[N],ans2[N]; inline bool cmp1(P a,P b){return a.x==b.x?a.y>b.y:a.x<b.x;} inline bool cmp2(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;} inline ll mul(P b){return(ll)now.x*b.x+(ll)now.y*b.y;} inline void Max(ll&a,ll b){if(a<b)a=b;} inline void Min(ll&a,ll b){if(a>b)a=b;} inline void read(int&a){ char c;bool f=0;a=0; while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-'))); if(c!='-')a=c-'0';else f=1; while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0'; if(f)a=-a; } inline void read(ll&a){ char c;bool f=0;a=0; while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-'))); if(c!='-')a=c-'0';else f=1; while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0'; if(f)a=-a; } inline void askmax1(ll&t){ for(int l=0,r=t1;l<=r&&t<C;){ len=(r-l)/3; if((s1=mul(q1[m1=l+len]))>(s2=mul(q1[m2=r-len])))Max(t,s1),r=m2-1;else Max(t,s2),l=m1+1; } } inline void askmax2(ll&t){ for(int l=0,r=t2;l<=r&&t<C;){ len=(r-l)/3; if((s1=mul(q2[m1=l+len]))>(s2=mul(q2[m2=r-len])))Max(t,s1),r=m2-1;else Max(t,s2),l=m1+1; } } inline void askmin1(ll&t){ for(int l=0,r=t1;l<=r&&t>C;){ len=(r-l)/3; if((s1=mul(q1[m1=l+len]))<(s2=mul(q1[m2=r-len])))Min(t,s1),r=m2-1;else Min(t,s2),l=m1+1; } } inline void askmin2(ll&t){ for(int l=0,r=t2;l<=r&&t>C;){ len=(r-l)/3; if((s1=mul(q2[m1=l+len]))<(s2=mul(q2[m2=r-len])))Min(t,s1),r=m2-1;else Min(t,s2),l=m1+1; } } void solve(int l,int r){ if(l==r)return; int mid=(l+r)>>1; solve(l,mid),solve(mid+1,r); for(cnt=0,i=l;i<=mid;i++)if(!a[i].q)b[cnt++]=P(a[i].a,a[i].b); if(!cnt)return; for(std::sort(b,b+cnt,cmp1),q1[t1=0]=b[0],i=1;i<cnt;i++)if(b[i].x!=b[i-1].x){ while(t1&&(ll)(q1[t1].y-q1[t1-1].y)*(b[i].x-q1[t1].x)<=(ll)(b[i].y-q1[t1].y)*(q1[t1].x-q1[t1-1].x))t1--; q1[++t1]=b[i]; } for(std::sort(b,b+cnt,cmp2),q2[t2=0]=b[0],i=1;i<cnt;i++)if(b[i].x!=b[i-1].x){ while(t2&&(ll)(q2[t2].y-q2[t2-1].y)*(b[i].x-q2[t2].x)>=(ll)(b[i].y-q2[t2].y)*(q2[t2].x-q2[t2-1].x))t2--; q2[++t2]=b[i]; } for(i=r;i>mid;i--)if(a[i].q){ now=P(a[i].a,a[i].b),C=a[i].c; if(a[i].b>0)askmin2(ans1[i]),askmax1(ans2[i]);else askmin1(ans1[i]),askmax2(ans2[i]); } } int main(){ read(n),read(m); for(i=1;i<=n;i++)read(A),read(B),a[i]=Q(A,B,0,0); for(i=1;i<=m;i++){ read(op),read(A),read(B); if(op==1)a[n+i]=Q(A,B,0,0);else read(C),a[n+i]=Q(A,B,C,1); ans1[n+i]=inf,ans2[n+i]=-inf; } solve(1,n+=m); for(i=1;i<=n;i++)if(a[i].q)puts(ans2[i]<a[i].c||ans1[i]>a[i].c?"YES":"NO"); return 0; }
相关文章
- Where is the global yarn config file? yarn
- What is the difference between npm install and npm run build?
- Configuration file schema for the .NET Framework
- Install the IIS 6.0 Management Compatibility Components in Windows 7 or in Windows Vista from Control Panel
- The property 'RowId' is part of the object's key information and cannot be modified.
- ZOJ 1654 Place the Robots建图思维(分块思想)+二分匹配
- LightOJ 1348 Aladdin and the Return Journey
- The connection to the server ip:6443 was refused - did you specify the right host or port
- The bean ‘XXXXX.FeignClientSpecification‘ could not be registered.
- the-type-java-lang-charsequence-cannot-be-resolved-in-package-declaration
- Docker服务启动报错:Job for docker.service failed because the control process exited with error code
- java.io.EOFException: Unexpected EOF read on the socket
- ERROR: The Python ssl extension was not compiled. Missing the OpenSSL lib?
- vmware Unable to open kernel device ".Globalvmx86": The system cannot find the file 的解决方法
- 【解决方案】ERROR: lib/bridge_generated.dart:837:9: Error: The parameter ‘ptr‘ of the method ‘FlutterRustB
- Tomcat 8 Invalid character found in the request target. The valid characters are defined in RFC 3986
- 【HDU - 4344】Mark the Rope(大整数分解)
- mysql导出数据报错The MySQL server is running with the --secure-file-priv option so it cannot execute this statement
- Removing the bias of integral pose regression阅读笔记
- The library 'xxx.jar' contains native libraries that will not run on the device. 解决方法(Eclipse)
- The incident LOST_EVENTS occured on the master. Message: error writing to the binary log, Error_code
- The total number of locks exceeds the lock table size,mysql update报错
- hdu 1556 Color the ball (技巧 || 线段树)
- Solve Warning: The elevation provided <Paper elevation={24}> is not available in the theme.
- DVWA文件包含报错The PHP function allow_url_include is not enabled.的解决方法