首页 > 代码库 > 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 数学