首页 > 代码库 > Uva1398 Meteor

Uva1398 Meteor

扫描线法。

将流星出现在相机里的时间转化成线段,离散化端点后,扫描何时出现的流星最多。注意边界的不算,所以要先减右端点再加左端点

 

 

 1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #define LL long long 8 using namespace std; 9 const int mxn=100010;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();}13     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();}14     return x*f;15 }16 int T;17 int n,w,h;18 struct node{19     int v,t;20 }c[mxn<<1];int cnt=0;21 int cmp(node a,node b){22     if(a.v==b.v)return a.t>b.t;23     return a.v<b.v;24 }25 //int h1[mxn],h2[mxn],w1[mxn],w2[mxn];26 int L,R;27 void init(int a,int x,int w){28     if(!a){ if(x<=0 || x>=w)R=L-1; }29     else if(a>0){30         L=max(L,-x*2520/a);31         R=min(R,(w-x)*2520/a);32     }33     else{34         L=max(L,(w-x)*2520/a);35         R=min(R,-x*2520/a);36     }37     return;38 }39 int main(){40     T=read();41     int i,j;42     int x,y,a,b;43     while(T--){44         cnt=0;//init45         w=read();h=read();n=read();46         for(i=1;i<=n;i++){47             x=read();y=read();a=read();b=read();48             L=0,R=0x7f7f7f7f;49             init(a,x,w);init(b,y,h);50             if(R>L){51                 c[++cnt].v=L;c[cnt].t=0;52                 c[++cnt].v=R;c[cnt].t=1;53             }54         }55         sort(c+1,c+cnt+1,cmp);56         int ans=0,ct=0;57         for(i=1;i<=cnt;i++){58             if(!c[i].t){//进入 59                 ++ct;60                 ans=max(ans,ct);61             }62             else --ct;63         }64         printf("%d\n",ans);65     }66     return 0;67 }

 

Uva1398 Meteor