由于到达点时不能绕墙,因为这是无意义的,所以,两点间的最小墙依然是按照直线所穿过的墙计算。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const double eps=0.000000001;
struct point{
double x,y;
}Point[100],des;
struct edge{
point start,end;
}Edge[100],Tmp; int ne,np; double multi(point p1,point p2, point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
} bool cross(edge v1, edge v2){
if(max(v1.start.x,v1.end.x)>=min(v2.start.x,v2.end.x)&&
max(v2.start.x,v2.end.x)>=min(v1.start.x,v1.end.x)&&
max(v1.start.y,v1.end.y)>=min(v2.start.y,v2.end.y)&&
max(v2.start.y,v2.end.y)>=min(v1.start.y,v1.end.y)&&
multi(v2.start,v1.end,v1.start)*multi(v1.end,v2.end,v1.start)>eps&&
multi(v1.start,v2.end,v2.start)*multi(v2.end,v1.end,v2.start)>eps)
return true;
return false;
} int main(){
while(scanf("%d",&ne)!=EOF){
np=0;
for(int i=0;i<ne;i++){
scanf("%lf%lf",&Point[np].x,&Point[np].y);
np++;
scanf("%lf%lf",&Point[np].x,&Point[np].y);
np++;
Edge[i].start=Point[np-2]; Edge[i].end=Point[np-1];
}
Point[np].x=0; Point[np].y=0;
np++;
Point[np].x=0; Point[np].y=100;
np++;
Point[np].x=100; Point[np].y=0;
np++;
Point[np].x=100; Point[np].y=100;
np++;
scanf("%lf%lf",&des.x,&des.y);
int ans=1000,tmp;
for(int i=0;i<np;i++){
Tmp.start=des; Tmp.end=Point[i]; tmp=0;
for(int i=0;i<ne;i++){
if(cross(Tmp,Edge[i]))
tmp++;
}
ans=min(ans,tmp);
}
printf("Number of doors = %d\n",ans+1);
}
}

  

最新文章

  1. 《Pro ASP.NET MVC 4》异常整理
  2. Spring MVC 1
  3. 【转】Polymer API开发指南 (一)(翻译)
  4. ok6410串口裸机总结
  5. MVC Model Binder
  6. android 37 线程通信Looper
  7. [转] UIImage 图像-IOS开发 (实例)
  8. Nginx负载均衡搭建(Window与Linux)
  9. (转)Windows 平台下解决httpd.exe: syntax error on line 39
  10. mysqldump详解之--master-data
  11. Docker从入门到飞升:基础配置安装
  12. MariaDB:在Linux下修改编码
  13. UIActivityIndicatorView 的使用
  14. 《Linux内核设计与实现》Chapter 2 读书笔记
  15. MVC ---- 标准查询运算符
  16. [CEOI2017]Building Bridges
  17. Effective STL 43: Prefer algorithm calls to hand-written loops
  18. 解决API中无法使用session问题
  19. .net core i上 K8S(七).netcore程序的服务发现
  20. php防止用户输入进行跨站攻击的方式

热门文章

  1. treap平衡树
  2. springboot创建项目
  3. Springboot统一跨域配置
  4. 基于Myeclipse+Axis2的WebService开发实录
  5. C - Xenia and Ringroad
  6. ASP.NET MVC + 工厂模式 + 三层 + 缓存
  7. SQLServer In和Exists
  8. 前端HTML5思维导图笔记
  9. 快速搭建tab
  10. node post和get请求原理