首页 > 代码库 > Gym 101334A Area 51 数学
Gym 101334A Area 51 数学
大致题意:
给出n个建筑的二维坐标,每个建筑名称为一个字母,不同坐标的建筑可以有同一名称,并保证这些坐标都是在y轴上半轴。给出一串建筑名称的字符串,在X轴上找出一个或多个区间,使Nick在这个区间上从左往右观看,看到的建筑顺序与给出的字符串相符合。
分析:
建筑物的数量最多100,那么我们可以先求出任意两点的连线与X轴的交点,每两个相邻的交点间的开区间看到的顺序是相同的。那么我们枚举所有区间即可。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define eps 1e-9using namespace std;const int maxn=100+5;const int INF=1e5;int n;char s[maxn];double cosA[maxn];double p[maxn*maxn];double ans[maxn*maxn];struct Facility{ char c; int x; int y;}fac[maxn];struct Angle{ char c; double cosA;}ang[maxn];bool cmp(Angle a,Angle b){ return a.cosA<b.cosA;}bool judge(double o){ for(int i=0;i<n;i++) { ang[i].c=fac[i].c; ang[i].cosA=(fac[i].x-o)/sqrt(fac[i].y*fac[i].y+(fac[i].x-o)*(fac[i].x-o)); //算区间中点与建筑的连线与X轴正方向的夹角的余弦值 } sort(ang,ang+n,cmp); for(int i=0;i<n;i++) if(ang[i].c!=s[i]) return false; return true;}int main(){// freopen("in.txt","r",stdin);// freopen("area.in","r",stdin);// freopen("area.out","w",stdout); while(~scanf("%d",&n)) { getchar(); scanf("%s",s); for(int i=0;i<n;i++) { getchar(); scanf("%c%d%d",&fac[i].c,&fac[i].x,&fac[i].y); } p[0]=-INF; int cnt=1; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(fac[i].y==fac[j].y) continue; p[cnt++]=1.0*(fac[j].x*fac[i].y-fac[i].x*fac[j].y)/(fac[i].y-fac[j].y); } } p[cnt++]=INF; sort(p,p+cnt); int cnt2=0; for(int i=0;i<cnt-1;i++) { if(p[i+1]-p[i]<eps) continue; if(judge((p[i]+p[i+1])/2)) //去区间中点来判断此区间是否合法 { ans[cnt2++]=p[i]; ans[cnt2++]=p[i+1]; } } printf("%d\n",cnt2/2); if(cnt2==0) continue; if(fabs(ans[0]-p[0])<eps) printf("%c ",‘*‘); else printf("%.7f ",ans[0]); for(int i=1;i<cnt2-1;i++) printf("%.7f ",ans[i]); if(fabs(ans[cnt2-1]-p[cnt-1])<eps) printf("%c\n",‘*‘); else printf("%.7f\n",ans[cnt2-1]); } return 0;}
Gym 101334A Area 51 数学
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。