1 条题解
-
0

#include<map> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define MAXN 50005 #define MAXM 100005 #define LL long long #define DB double #define ENDL putchar('\n') #define lowbit(x) ((-x)&(x)) //#define int LL //#pragma GCC optimize(2) LL read() { LL f = 1,x = 0;char s = getchar(); while(s < '0' || s > '9') {if(s=='-')f=-f;s = getchar();} while(s >= '0' && s <= '9') {x=x*10+(s-'0');s=getchar();} return f*x; } const int MOD = 998244353; int n,m,i,j,s,o,k; struct it{ DB x,y; it(){x = y = 0;} it(DB X,DB Y){x=X;y=Y;} }; it cg(it a,it b) { DB k = (a.y - b.y) / (a.x - b.x); DB B = a.y - a.x * k; return it(k,B); } it jd(it a,it b) { DB xx = (b.y - a.y) / (a.x - b.x); return it(xx,a.x*xx+a.y); } bool abov(it a,it st) { DB y2 = a.x * st.x + st.y; return a.y >= y2; } bool operator < (it a,it b) {return a.y < b.y;} bool operator > (it a,it b) {return b < a;} bool operator <= (it a,it b) {return a.y <= b.y;} bool operator >= (it a,it b) {return b <= a;} struct tr{ int l,r; it st; tr(){l=r=0;st=it(0,-1e9);} }tre[MAXM<<4]; void maketree(int a,int l,int r) { tre[a].l = l;tre[a].r = r; if(l < r) { int mid = (l+r)>>1; maketree(a<<1,l,mid); maketree(a<<1|1,mid+1,r); } return ; } void addtree(int a,int l,int r,it st) { if(tre[a].l > r || tre[a].r < l) return ; if(tre[a].l >= l && tre[a].r <= r) { DB ll = (DB)tre[a].l,rr = (DB)tre[a].r; it l1 = it(ll,ll*tre[a].st.x+tre[a].st.y); it r1 = it(rr,rr*tre[a].st.x+tre[a].st.y); it l2 = it(ll,ll*st.x+st.y),r2 = it(rr,rr*st.x+st.y); if(l1 >= l2 && r1 >= r2) return ; if(l2 >= l1 && r2 >= r1) { tre[a].st = st; return ; } it md = jd(st,tre[a].st); int mid = (tre[a].l+tre[a].r)>>1; it ls = (l1 >= l2 ? tre[a].st:st),rs = (r1 >= r2 ? tre[a].st:st); if(md.x <= (DB)mid) tre[a].st = rs,addtree(a<<1,l,r,ls); else tre[a].st = ls,addtree(a<<1|1,l,r,rs); return ; } addtree(a<<1,l,r,st);addtree(a<<1|1,l,r,st); return ; } DB query(int a,int ad) { if(tre[a].l > ad || tre[a].r < ad) return -1e9; if(tre[a].l == tre[a].r) { return ad*tre[a].st.x + tre[a].st.y; } return max(ad*tre[a].st.x+tre[a].st.y,max(query(a<<1,ad),query(a<<1|1,ad))); } int main() { n = read();m = read(); maketree(1,1,100000); for(int i = 1;i <= n;i ++) { it a,b; a.x = (DB)read(); a.y = (DB)read(); b.x = (DB)read(); b.y = (DB)read(); if(a.x > b.x) swap(a,b); it st; if(a.x == b.x) st = it(0,max(a.y,b.y)); else st = cg(a,b); int ll = (int)a.x,rr = (int)b.x; addtree(1,ll,rr,st); } for(int i = 1;i <= m;i ++) { k = read(); if(!k) { it a,b; a.x = (DB)read(); a.y = (DB)read(); b.x = (DB)read(); b.y = (DB)read(); if(a.x > b.x) swap(a,b); it st; if(a.x == b.x) st = it(0,max(a.y,b.y)); else st = cg(a,b); int ll = (int)a.x,rr = (int)b.x; addtree(1,ll,rr,st); } else { int x0 = read(); DB ans = query(1,x0); printf("%.4f\n",ans < -1e8 ? 0.0:ans); } } return 0; }
- 1
信息
- ID
- 10092
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 14
- 已通过
- 3
- 上传者