<\/span><\/h2>\n\u59dc\u5927\u7237\u8bb2\u5b8c\uff0c\u611f\u89c9\u9898\u89e3\u597d\u5de7\u5999<\/p>\n
\u9996\u5148\u6211\u4eec\u5bf9\u4e8e\u5220\u9664\u64cd\u4f5c\u53ef\u4ee5\u7528\u7ebf\u6bb5\u6811\u5206\u6cbb\u6765\u5b9e\u73b0<\/p>\n
\u7136\u540e\u95ee\u9898\u7684\u600e\u4e48\u67e5\u8be2<\/p>\n
\u5bf9\u4e8e\u4e00\u4e2a\u5411\u91cf\u7684\u6700\u4f18\u503c\uff0c\u662f\u5728\u4e0e\u8be5\u5411\u91cf\u5782\u76f4\u7684\u7ebf\u4e2d\uff0c\u5728\u8ddd\u79bb\u6700\u8fdc\u7684\u7ebf\u4e0a\u7684\u70b9\u7684\u70b9\u79ef<\/p>\n
\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u7ef4\u62a4\u51fa\u51f8\u5305\uff0c\u7136\u540e\u5728\u51f8\u5305\u4e0a\u4e09\u5206<\/p>\n
\u90a3\u4e48\uff0c\u6211\u4eec\u7b2c\u4e00\u79cd\u60f3\u6cd5\u662f\u7ebf\u6bb5\u6811\u5206\u6cbb\u65f6\u5408\u5e76\u51f8\u5305\uff0c\u6216\u5e73\u8861\u6811\u7ef4\u62a4\u51f8\u5305\uff1f<\/p>\n
\u4f46\u662f\u8fd9\u4e2a\u592a\u96be\u4e86\uff0c\u4f5c\u4e3a\u849f\u84bb\u6211\u5f53\u7136\u4e0d\u4f1a\u4e86qaq<\/p>\n
\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u5728\u7ebf\u6bb5\u6811\u4e0a\u6bcf\u4e00\u4e2a\u70b9\u7ef4\u62a4\u4e00\u4e2a\u51f8\u5305\uff0c\u5728\u67e5\u8be2\u7684\u65f6\u5019\u53bb\u627e\u4ece\u6839\u5230\u53f6\u5b50\u8282\u70b9\u8def\u5f84\u4e0a\u6bcf\u4e00\u4e2a\u7684\u6700\u4f18\u503c\u53bb\u53d6\u4e00\u4e2amax\u5c31\u597d\u5566<\/p>\n
\u6700\u540e\u65f6\u95f4\u590d\u6742\u5ea6O(nlog\u00b2n)<\/p>\n
#include<map>\r\n#include<cmath>\r\n#include<queue>\r\n#include<cstdio>\r\n#include<vector>\r\n#include<cstring>\r\n#include<iostream>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define inf 1000000007\r\n#define ll long long\r\n#define N 200010\r\ninline int rd()\r\n{\r\n\tint x=0,f=1;char ch=getchar();\r\n\twhile(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}\r\n\twhile(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}\r\n\treturn x*f;\r\n}\r\nstruct qaz{int x,y,l,r;}e[N],ak[N]; \r\nll cj(int x,int y,int xx,int yy){return (ll)x*yy-(ll)y*xx;}\r\nint n,tot,ta,xmn,ymn;\r\nbool cmp(qaz a,qaz b)\r\n{\r\n\treturn cj(a.x-xmn,a.y-ymn,b.x-xmn,b.y-ymn)>0;\r\n}\r\nvector<int>st[N<<2],tb[N<<2];\r\n#define ls p<<1\r\n#define rs p<<1|1\r\nvoid add(int p,int l,int r,int L,int R,int x)\r\n{\r\n\tif(l==L&&r==R){st[p].push_back(x);return;}\r\n\tint mid=l+r>>1;\r\n\tif(R<=mid) add(ls,l,mid,L,R,x);\r\n\telse if(L>mid) add(rs,mid+1,r,L,R,x);\r\n\telse add(ls,l,mid,L,mid,x),add(rs,mid+1,r,mid+1,R,x);\r\n}\r\nint q[N];\r\nbool ck(int p,int a,int b,int c)\r\n{\r\n\tint X1,Y1,X2,Y2;\r\n\tX1=e[st[p][b]].x-e[st[p][c]].x;\r\n\tX2=e[st[p][a]].x-e[st[p][c]].x;\r\n\tY1=e[st[p][b]].y-e[st[p][c]].y;\r\n\tY2=e[st[p][a]].y-e[st[p][c]].y;\r\n\treturn cj(X1,Y1,X2,Y2)<0;\r\n}\r\nvoid build(int p,int l,int r)\r\n{\r\n\tif(st[p].size()<=2) tb[p]=st[p];\r\n\telse \r\n\t{\r\n\t\tq[0]=0;q[1]=1;int r=1;\r\n\t\tst[p].push_back(st[p][0]);\r\n\t\tfor(int i=2;i<st[p].size();i++)\r\n\t\t{\r\n\t\t\twhile(r&&ck(p,i,q[r],q[r-1])) r--;\r\n\t\t\tq[++r]=i;\r\n\t\t}\r\n\t\tfor(int i=0;i<=r;i++) tb[p].push_back(st[p][q[i]]);\r\n\t}\r\n\tif(l==r) return;\r\n\tint mid=l+r>>1;\r\n\tbuild(ls,l,mid);\r\n\tbuild(rs,mid+1,r);\r\n}\r\nll ans;\r\nll Dot(qaz a,qaz b){return (ll)a.x*b.x+(ll)a.y*b.y;}\r\nvoid fd(int p,int l,int r,qaz c)\r\n{\r\n\tint L=0,R=tb[p].size()-1,m1,m2;\r\n\twhile(L+3<=R)\r\n\t{\r\n\t\tm1=(L+L+R)\/3;m2=(L+R+R)\/3;\r\n\t\tif(Dot(e[tb[p][m1]],c)<=Dot(e[tb[p][m2]],c)) L=m1;\r\n\t\telse R=m2;\r\n\t}\r\n\tfor(int i=L;i<=R;++i)ans=max(ans,Dot(e[tb[p][i]],c));\r\n\tif(l==r) return;\r\n\tint mid=l+r>>1;\r\n\tif(c.l<=mid) fd(ls,l,mid,c);\r\n\telse fd(rs,mid+1,r,c);\r\n}\r\nvoid ask(int x)\r\n{\r\n\tans=0;\r\n\tfd(1,1,n,ak[x]);\r\n\tprintf(\"%lld\\n\",ans);\r\n}\r\nint main()\r\n{\r\n\tn=rd();\r\n\tint x,y,op;\r\n\tfor(int i=1;i<=n;i++)\r\n\t{\r\n\t\top=rd();x=rd();\r\n\t\tif(op^2) y=rd();\r\n\t\tif(op==1)\r\n\t\t{\r\n\t\t\te[++tot]=(qaz){x,y,i,n};\r\n\t\t\txmn=min(x,xmn);\r\n\t\t\tymn=min(y,ymn);\r\n\t\t}\r\n\t\telse if(op==2) e[x].r=i-1;\r\n\t\telse ak[++ta]=(qaz){x,y,i,0};\r\n\t}\r\n\tsort(e+1,e+tot+1,cmp);\r\n\tfor(int i=1;i<=tot;i++)\r\n\t\tadd(1,1,n,e[i].l,e[i].r,i);\r\n\tbuild(1,1,n);\r\n\tfor(int i=1;i<=ta;i++) ask(i);\r\n\treturn 0;\r\n}<\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
4311: \u5411\u91cf Time Limit:\u00a020 Sec\u00a0\u00a0Memory Limit:\u00a0512 MB Descr […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[28,8,27],"class_list":["post-335","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-28","tag-8","tag-27"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=335"}],"version-history":[{"count":1,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/335\/revisions"}],"predecessor-version":[{"id":336,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/335\/revisions\/336"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}