大致题意:

给出n个建筑的二维坐标,每个建筑名称为一个字母,不同坐标的建筑可以有同一名称,并保证这些坐标都是在y轴上半轴。给出一串建筑名称的字符串,在X轴上找出一个或多个区间,使Nick在这个区间上从左往右观看,看到的建筑顺序与给出的字符串相符合。

分析:

建筑物的数量最多100,那么我们可以先求出任意两点的连线与X轴的交点,每两个相邻的交点间的开区间看到的顺序是相同的。那么我们枚举所有区间即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define eps 1e-9
using 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;
}

最新文章

  1. Python 静态方法、类方法
  2. 未封装的js放大镜特效
  3. zencart安装后修改configure.php权限
  4. Childlife旗下三驾马车
  5. JavaScript基础(二)
  6. 行内人解读开发一个App需要多少钱?
  7. 优秀的 Android Studio 插件
  8. linux nc命令使用详解
  9. 小程序新能力-个人开发者尝鲜微信小程序
  10. linux nfs远程挂载和卸载
  11. Gradle: Gradle Wrapper
  12. [UE4]更新Flag坐标
  13. 23.模拟登录cookies请求速询网站数据
  14. (HttpURLConnection)强制转化
  15. Python进阶内容(一)--- 高阶函数 High order function
  16. jquery移除、绑定、触发元素事件
  17. js中的class
  18. 问题 F: 等比数列
  19. POJ 1067 取石子游戏 (威佐夫博奕,公式)
  20. 解读SDN核心技术:OpenFlow深入分析(转载)

热门文章

  1. sosreport -a --report
  2. ansible-一键完成LNMP架构_期中架构
  3. 10.6 ip:网络配置工具
  4. 物联网技术nbiot与LoRa的区别有哪些
  5. Servlet中的过滤器和监听器
  6. docker-ce 安装
  7. 策略模式干掉if-else,switch
  8. MegEngine推理性能优化
  9. ADAS测试
  10. MindSpore平台系统类