首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。