1995. Yukari

★★☆ 输入文件：camera.in 输出文件：camera.out 简单对比
时间限制：1 s 内存限制：128 MB

题目背景：

幻想乡的创始人之一，八云紫，有着强大的控制结界的能力，可以瞬间消除一定范围内所有弹幕。我们可以将其消除范围视为一个矩形，而弹幕可以视为动点。

八云紫想要嘲讽她的敌人，所以她希望只使用一次消除能力，尽可能多地消除弹幕。

请你告诉她，在哪一时刻使用道具，可以消除尽可能多的弹幕。

问题描述：

在平面上给定一个矩形区域(也可能退化成线段或者点)。

矩形的边与坐标轴平行，左下端点为 (xl,yl)，右上端点为 (xr,yr)。

给定 n 个动点，初始坐标为 (xi, yi)，运动方向为 (ui,vi)，速度为 sqrt((ui)^2+(vi)^2)

求在哪一时刻 t (t ∈ N)，在矩形内部及边界的动点数目最多。

如果有多个 t 满足条件，输出最小的 t 即可。

输入格式：

第一行 5 个正整数，n, xl, yl, xr, yr，表示动点个数和矩形区域。

接下来 n 行，每行 4 个整数，xi, yi, ui, vi ，描述第 i 个动点。

输出格式：

在矩形内部及边界的动点数目最多的时刻 t (t ∈ N)。

如果有多个 t 满足条件，输出最小的 t 即可。

样例数据1：

camera.in

camera.out

2 2 2 3 3

3 1 -1 1

2 3 1 -1

样例数据2：

camera.in

camera.out

13 44 68 49 73

40 46 2 6

28 75 4 -1

32 61 3 3

41 64 2 1

40 99 2 -7

54 49 -2 6

32 80 4 -2

73 99 -7 -7

23 93 6 -5

44 96 0 -6

36 70 3 0

70 98 -6 -7

75 53 -7 4

数据范围：

对于前 40% 数据，

1<= n <= 100, 1 <= xl, xr, yl, yr, xi, yi <= 100, -10 <= ui, vi <= 10

对于100% 数据,

1<= n <= 10^5, 1 <= xl, xr, yl, yr, xi, yi <= 10^9, 0 <= |ui|, |vi|<= 10^5, xl <= xr, yl <= yr

保证 n，xl，xr，yl，yr，xi，yi，ui，vi 均为整数.

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define maxn 1000010

using namespace std;

int n,xl,yl,xr,yr;

int tot,cnt,sum[maxn],cnt1;

double l[maxn],r[maxn],h[maxn*],h1[maxn*];

int find(int x){

    int l=,r=cnt,res=;

    while(l<=r){

        int mid=(l+r)>>;

        if(h[mid]<=x)res=mid,l=mid+;

        else r=mid-;

    }

    return res;

}

int main(){

    //freopen("camera.in","r",stdin);freopen("camera.out","w",stdout);

    freopen("Cola.txt","r",stdin);

    scanf("%d%d%d%d%d",&n,&xl,&yl,&xr,&yr);

    int x,y,u,v;

    int t1,t2,sx1,sx2,sy1,sy2;

    memset(r,,sizeof(r));

    for(int i=;i<=n;i++){

        scanf("%d%d%d%d",&x,&y,&u,&v);

        if((x<xl&&u<=)||(x>xr&&u>=)||(y<yl&&v<=)||(y>yr&&v>=))continue;

        tot++;

        if(x<=xr&&x>=xl&&y<=yr&&y>=yl){

            l[tot]=;

            if(u>)r[tot]=min(r[tot],(double)(xr-x)/u);

            if(u<)r[tot]=min(r[tot],(double)(xl-x)/u);

            if(v>)r[tot]=min(r[tot],(double)(yr-y)/v);

            if(v<)r[tot]=min(r[tot],(double)(yl-y)/v);

        }

        else{

            if(u>){//向右飞

                l[tot]=max(l[tot],(double)(xl-x)/u);//飞到左边界

                r[tot]=min(r[tot],(double)(xr-x)/u);//飞到右边界

            }

            if(u<){//向左飞

                l[tot]=max(l[tot],(double)(xr-x)/u);//飞到右边界

                r[tot]=min(r[tot],(double)(xl-x)/u);//飞到左边界

            }

            if(v>){//向上飞

                l[tot]=max(l[tot],(double)(yl-y)/v);

                r[tot]=min(r[tot],(double)(yr-y)/v);

            }

            if(v<){//向下飞

                l[tot]=max(l[tot],(double)(yr-y)/v);

                r[tot]=min(r[tot],(double)(yl-y)/v);

            }

        }

    }

    //for(int i=1;i<=n;i++)printf("%.2lf %.2lf\n",l[i],r[i]);

    for(int i=;i<=tot;i++){

        h1[++cnt1]=l[i];

        h1[++cnt1]=r[i];

    }

    sort(h1+,h1+cnt1+);

    h[++cnt]=h1[];

    for(int i=;i<=cnt1;i++)

        if(h1[i]!=h1[i-])h[++cnt]=h1[i];

    for(int i=;i<=tot;i++){

        int pos=find(l[i]);

        sum[pos]++;

        pos=find(r[i]);

        sum[pos+]--;

    }

    int mx=,id=;

    for(int i=;i<=n;i++){

        sum[i]+=sum[i-];

        if(sum[i]>mx)mx=sum[i],id=i;

    }

    printf("%.0lf",h[id]);

}

30分算出所有弹幕出现的时间段+离散化+差分

#include<cstdio>

#include<algorithm>

using namespace std;

int INF=0x7fffffff;

int in[]={},out[]={};

int a[]={};

int main(){

    freopen("camera.in","r",stdin);

    freopen("camera.out","w",stdout);

    int i,n,xl,yl,xr,yr,cnt=,sum=,maxc=,ans;

    scanf("%d%d%d%d%d",&n,&xl,&yl,&xr,&yr);

    for(i=;i<n;i++){

        int x,y,u,v;

        int txs=-,txe=INF,tys=-,tye=INF,ts=-,te=-;

        scanf("%d%d%d%d",&x,&y,&u,&v);

        if((x<xl&&u<=)||(x>xr&&u>=))continue;

        if((y<yl&&v<=)||(y>yr&&v>=))continue;

        if(x>=xl&&x<=xr&&y>=yl&&y<=yr){

            ts=;

            if(u==&&v==)te=INF;

            else if(u==){

                if(v>)te=(yr-y)/v;

                else{v=-v;te=(y-yl)/v;}

            }

            else if(v==){

                if(u>)te=(xr-x)/u;

                else{u=-u;te=(x-xl)/u;}

            }

            else{

                if(u>)txe=(xr-x)/u;

                else{u=-u;txe=(x-xl)/u;}

                if(v>)txe=(yr-y)/v;

                else{v=-v;tye=(y-yl)/v;}

                te=min(txe,tye);

            }

        }

        else{

            if(u<)u=-u;

            if(v<)v=-v;

            if(u==){

                if(y

                <=yl){tys=(yl-y+v-)/v;tye=(yr-y)/v;}

                if(y>=yr){tys=(y-yr+v-)/v;tye=(y-yl)/v;}

            }

            else if(v==){

                if(x<=xl){txs=(xl-x+u-)/u;txe=(xr-x)/u;}

                if(x>=xr){txs=(x-xr+u-)/u;txe=(x-xl)/u;}

            }

            else{

                if(x<=xl){txs=(xl-x+u-)/u;txe=(xr-x)/u;}

                if(x>=xr){txs=(x-xr+u-)/u;txe=(x-xl)/u;}

                if(y<=yl){tys=(yl-y+v-)/v;tye=(yr-y)/v;}

                if(y>=yr){tys=(y-yr+v-)/v;tye=(y-yl)/v;}

            }

            ts=max(txs,tys);

            te=min(txe,tye);

        }

        in[cnt]=ts;out[cnt++]=te;

    }

    for(i=;i<=cnt-;i++){a[in[i]]++;a[out[i]+]--;}

    for(i=;i<=cnt-;i++){sum+=a[i];if(sum>maxc){maxc=sum;ans=i;}}

    printf("%d",ans);

    return ;

}

巴特西

Cogs 1995. Yukari

1995. Yukari

最新文章

热门文章