栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3379 Master Spark

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3379 Master Spark

#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<vector>#include<string>using namespace std;typedef long long lld;#define pb push_back#define mp make_pair#define X first#define Y second#define pi acos(-1.0)#define eps 1e-8#define maxn 30010int Sig(double a){if(a < -eps)return -1;return a > eps;}struct Event{double s;int id,flag;Event(){}Event(double s0,int id0,int flag0):s(s0),id(id0),flag(flag0){}}pp[1000010];int qq;bool cmp(Event a,Event b){return a.s < b.s;}double x[maxn];double y[maxn];bool in[maxn];int main(){int n;double a;while(scanf("%d %lf",&n,&a)!=EOF){for(int i=0;i<n;i++)scanf("%lf",&x[i]);for(int i=0;i<n;i++)scanf("%lf",&y[i]);int add=0;qq=0;for(int i=0;i<n;i++){if(Sig(x[i]) == 0 && Sig(y[i]) == 0){add++;continue;}double R=sqrt(x[i]*x[i]+y[i]*y[i]);double left=0;double right=pi*0.5;int T=100;while(T--){double mid=(left+right)*0.5;double x1=R*cos(mid);double y1=R*sin(mid);if(Sig(y1-x1*x1*a) > 0)right=mid;elseleft=mid;}double angle=atan2(y[i],x[i]);double len=pi*0.5-(left+right)*0.5;pp[qq++]=Event(angle-len-1e-12,i,1);pp[qq++]=Event(angle+len+1e-12,i,-1);}int ans=0;memset(in,false,sizeof(in));int cnt=0;for(int i=0;i<qq;i++){pp[i+qq]=pp[i];pp[i+qq].s+=pi*2.0;}sort(pp,pp+qq+qq,cmp);for(int i=0;i<qq+qq;i++){ans=max(ans,cnt);int id=pp[i].id;if(pp[i].flag == 1){if(!in[id])cnt++;in[id]=true;}else{if(in[id])cnt--;in[id]=false;}ans=max(ans,cnt);}printf("%d dazen",ans+add);}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/368117.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号