新闻门户网站建设方案,郴州竞价网站建设方案,厦门小微企业网站建设补贴,建站标准正题
题目链接:http://www.ybtoj.com.cn/contest/119/problem/3 题目大意
给出nnn个点(xi,yi)(x_i,y_i)(xi,yi)#xff0c;mmm次给出(ki,ai)(k_i,a_i)(ki,ai)表示标记所有满足 yjkixjaiy_j\frac{k_i}{x_j^{a_i}}yjxjaiki的未标记点
求每个点…正题
题目链接:http://www.ybtoj.com.cn/contest/119/problem/3 题目大意
给出nnn个点(xi,yi)(x_i,y_i)(xi,yi)mmm次给出(ki,ai)(k_i,a_i)(ki,ai)表示标记所有满足 yjkixjaiy_j\frac{k_i}{x_j^{a_i}}yjxjaiki的未标记点
求每个点的标记时间
1≤n,m≤105,1ai101\leq n,m\leq 10^5,1a_i101≤n,m≤105,1ai10 解题思路
全是乘法所以可以先左右取lnlnln就是 ln(yj)ln(ki)−ln(xj)×ailn(y_j)ln(k_i)-ln(x_j)\times a_iln(yj)ln(ki)−ln(xj)×ai 把x,y,kx,y,kx,y,k取lnlnln然后就是一个顺眼的式子 xj×aiyikix_j\times a_iy_ik_ixj×aiyiki 虽然原题说(xi,yi)(x_i,y_i)(xi,yi)是点但是我们可以换个思路把(xi,yi)(x_i,y_i)(xi,yi)看成边f(z)xizyif(z)x_izy_if(z)xizyi(ai,ki)(a_i,k_i)(ai,ki)看成是点然后问在每条边下面的编号最小的点是哪个。
这个就很好解决了考虑整体二分。每次要考虑对于一条边是否有在[L,mid][L,mid][L,mid]编号的点在它下面。可以对于所有的[L,mid][L,mid][L,mid]的点拿出来构成一个下凸壳然后根据每条边的斜率二分出一个最下面的点然后只拿这个点判断就好了。
这样就是O(nlog2n)O(n\log^2 n)O(nlog2n)的了如果肯写归并排序和凸壳用单调队列维护是可以做到O(nlogn)O(n\log n)O(nlogn)的 code
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N1e510;
int n,m,f[N],s[N],p[N],p1[N],p2[N],top,pos[N];
double x[N],y[N],k[N],z[N];
double xj(double x1,double y1,double x2,double y2)
{return x1*y2-x2*y1;}
double xl(int a,int b,int c){double y1k[b]-k[a],x1z[b]-a[z];double y2k[c]-k[a],x2z[c]-z[a];return xj(x1,y1,x2,y2);
}
bool cmp(int x,int y)
{return z[x]z[y];}
void solve(int Ln,int Rn,int Lm,int Rm){if(LnRn)return;if(LmRm){for(int iLn;iRn;i)f[p[i]]Lm;return;}int mid(LmRm)1;top0;sort(posLm,pos1mid,cmp);for(int iLm;imid;i){while(top1xl(s[top-1],s[top],pos[i])0)top--;s[top]pos[i];}sort(posLm,pos1mid);int cnt10,cnt20;for(int iLn;iRn;i){int l1,rtop-1;while(lr){int m(lr)1;if(xj(z[s[m1]]-z[s[m]],k[s[m1]]-k[s[m]],1,x[p[i]])0)lm1;else rm-1;}if(x[p[i]]*z[s[l]]y[p[i]]k[s[l]])p1[cnt1]p[i];else p2[cnt2]p[i];}for(int i1;icnt1;i)p[iLn-1]p1[i];for(int i1;icnt2;i)p[Lncnt1i-1]p2[i];solve(Ln,Lncnt1-1,Lm,mid);solve(Lncnt1,Rn,mid1,Rm);return;
}
int main()
{freopen(analysis.in,r,stdin);
// freopen(analysis.out,w,stdout);scanf(%d%d,n,m);for(int i1;in;i){scanf(%lf%lf,x[i],y[i]);x[i]log(x[i]);y[i]log(y[i]);p[i]i;}for(int i1;im;i){scanf(%lf%lf,k[i],z[i]);k[i]log(k[i]);pos[i]i;}solve(1,n,1,m);for(int i1;in;i)if(f[i]m)puts(-1);else printf(%d\n,f[i]);return 0;
}
