首页 > 代码库 > ZOJ3379 Master Spark

ZOJ3379 Master Spark

2024-07-12 02:41:35   222人阅读

(¦3[____]←  扫描线问题，抛物线方程为 y=a*x*x 形式，

对每个点求出抛物线中轴的范围theta-delta~theta+delta，

theta = atan2(y,x)，delta则用方程组可解x*x+y*y=z*z+(a*z*z)^2，tan(theta)=z/(a*z*z)，故theta = atan2(1,a*z)

然后从-PI到PI进行扫描，用最小堆维护即可

这题调了好久啊，把>写成<，把double写成int。。。= =、捉鸡

#include<cstdio>#include<cmath>#include<cstring>#include<vector>#include<utility>#include<iostream>#include<algorithm>using namespace std;const int N=30010;const double TPI = 2*acos(-1);double x[N],y[N];vector<pair<double,double> > ang;int cnt;double heap[N];void heap_add(double a){    heap[++cnt]=a;    int u,ch=cnt;    double t=heap[cnt];    u = cnt>>1;    while(u&&heap[u]>t) {        heap[ch]=heap[u];        ch>>=1;        u=ch>>1;    }    heap[ch]=t;}void heap_pop(){    heap[1]=heap[cnt];    --cnt;    int u=1,chl,chr,ch;    double t=heap[1];    while(cnt) {        chl=u<<1;        chr=chl|1;        if(chr<=cnt&&heap[chl]<heap[chr]) ch=chl;        else if(chr<=cnt&&heap[chl]>heap[chr]) ch=chr;        else if(chl<=cnt) ch=chl;        else {            heap[u]=t;            break;        }        if(t>heap[ch]) {            heap[u]=heap[ch];            u=ch;        }        else {            heap[u]=t;            break;        }    }}int main(){    int n,ans;    double a,theta,delta,z;    while(scanf("%d%lf",&n,&a)==2) {        ang.clear();        cnt = 0;        for(int i=0;i<n;++i)            scanf("%lf",x+i);        for(int i=0;i<n;++i)            scanf("%lf",y+i);        for(int i=0;i<n;++i) {            theta=atan2(y[i],x[i]);            z=sqrt((sqrt(1+4*a*a*(x[i]*x[i]+y[i]*y[i]))-1)/(2*a*a));            delta = atan2(1,a*z);            ang.push_back(make_pair(remainder(theta-delta,TPI),remainder(theta+delta,TPI)));            if(ang.back().first>ang.back().second) {                heap_add(ang.back().second);                ang.back().second+=TPI;            }        }        ans = cnt;        sort(ang.begin(),ang.end());        for(vector<pair<double,double> >::iterator it=ang.begin();it!=ang.end();++it) {            heap_add(it->second);            while(cnt&&heap[1] < it->first) {                heap_pop();            }            ans=max(ans,cnt);        }        printf("%d daze\n",ans);    }}

 


联系
我们