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

zoj 3580 Angry Birds

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

zoj 3580 Angry Birds

#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<map>#include<set>#include<vector>using namespace std;typedef long long lld;#define eps 1e-14#define pi acos(-1.0)#define G 9.8#define inf 0xfffffffint Sig(double a){if(a < -eps)return -1;return a > eps;}double l[110];double r[110];int dp[1<<16];double V,Y;double solve(double angle){double vx=V*cos(angle);double vy=V*sin(angle);double a=0.5*G;double b=vy;double c=-Y;double delta=b*b-4.0*a*c;if(Sig(delta) < 0)return -1;double t=(-b+sqrt(delta))/(2.0*a);return vx*t;}double pp[100010];int qq;double get(double x){double left=0;double right=pi/2;int T=1000;while(T--){double mid=(left+right)*0.5;if(solve(mid) < x)right=mid;elseleft=mid;}//printf("%.4fn",(left+right)*0.5);return (left+right)*0.5;}int n;int get_mask1(double now){double x=now-pi/12;double y=now;double z=now+pi/12;int mask=0;double at;if(Sig(x) >= 0 && Sig(x-pi*0.5) <= 0){at=solve(x);for(int i=0;i<n;i++)if(Sig(l[i]-at) < 0 && Sig(at-r[i]) < 0)mask|=1<<i;}if(Sig(y) >= 0 && Sig(y-pi*0.5) <= 0){at=solve(y);for(int i=0;i<n;i++)if(Sig(l[i]-at) < 0 && Sig(at-r[i]) < 0)mask|=1<<i;}if(Sig(z) >= 0 && Sig(z-pi*0.5) <= 0){at=solve(z);for(int i=0;i<n;i++)if(Sig(l[i]-at) < 0 && Sig(at-r[i]) < 0)mask|=1<<i;}return mask;}int get_mask2(double now){double x=now+pi/12;double y=now;double z=now+pi/6;int mask=0;double at;if(Sig(x) >= 0 && Sig(x-pi*0.5) <= 0){at=solve(x);for(int i=0;i<n;i++)if(Sig(l[i]-at) < 0 && Sig(at-r[i]) < 0)mask|=1<<i;}if(Sig(y) >= 0 && Sig(y-pi*0.5) <= 0){at=solve(y);for(int i=0;i<n;i++)if(Sig(l[i]-at) < 0 && Sig(at-r[i]) < 0)mask|=1<<i;}if(Sig(z) >= 0 && Sig(z-pi*0.5) <= 0){at=solve(z);for(int i=0;i<n;i++)if(Sig(l[i]-at) < 0 && Sig(at-r[i]) < 0)mask|=1<<i;}return mask;}int get_mask3(double now){double x=now-pi/6;double y=now;double z=now-pi/12;int mask=0;double at;if(Sig(x) >= 0 && Sig(x-pi*0.5) <= 0){at=solve(x);for(int i=0;i<n;i++)if(Sig(l[i]-at) < 0 && Sig(at-r[i]) < 0)mask|=1<<i;}if(Sig(y) >= 0 && Sig(y-pi*0.5) <= 0){at=solve(y);for(int i=0;i<n;i++)if(Sig(l[i]-at) < 0 && Sig(at-r[i]) < 0)mask|=1<<i;}if(Sig(z) >= 0 && Sig(z-pi*0.5) <= 0){at=solve(z);for(int i=0;i<n;i++)if(Sig(l[i]-at) < 0 && Sig(at-r[i]) < 0)mask|=1<<i;}return mask;}int main(){while(scanf("%d %lf %lf",&n,&V,&Y)!=EOF){for(int i=0;i<n;i++)scanf("%lf %lf",&l[i],&r[i]);qq=0;for(int i=0;i<n;i++){pp[qq++]=get(l[i])+eps*10;pp[qq++]=get(l[i])-eps*10;pp[qq++]=get(r[i])+eps*10;pp[qq++]=get(r[i])-eps*10;}for(int mask=0;mask<(1<<n);mask++)dp[mask]=inf;for(int i=0;i<qq;i++){dp[get_mask1(pp[i])]=1;dp[get_mask2(pp[i])]=1;dp[get_mask3(pp[i])]=1;dp[get_mask1(pp[i])]=1;dp[get_mask2(pp[i]-pi/12)]=1;dp[get_mask3(pp[i]+pi/12)]=1;dp[get_mask1(pp[i])]=1;dp[get_mask2(pp[i]-pi/12)]=1;dp[get_mask3(pp[i]+pi/12)]=1;}dp[0]=0;for(int mask=1;mask<(1<<n);mask++){for(int x=mask;;x=(x-1)&mask){int y=mask^x;if(dp[x] != inf && dp[y] != inf)dp[mask]=min(dp[mask],dp[x]+dp[y]);if(x == 0)break;}}if(dp[(1<<n)-1] == inf)printf("-1n");elseprintf("%dn",dp[(1<<n)-1]);}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/379046.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

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

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