POJ 1066
2024-08-31 05:04:12
由于到达点时不能绕墙,因为这是无意义的,所以,两点间的最小墙依然是按照直线所穿过的墙计算。
#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);
}
}
最新文章
- 《Pro ASP.NET MVC 4》异常整理
- Spring MVC 1
- 【转】Polymer API开发指南 (一)(翻译)
- ok6410串口裸机总结
- MVC Model Binder
- android 37 线程通信Looper
- [转] UIImage 图像-IOS开发 (实例)
- Nginx负载均衡搭建(Window与Linux)
- (转)Windows 平台下解决httpd.exe: syntax error on line 39
- mysqldump详解之--master-data
- Docker从入门到飞升:基础配置安装
- MariaDB:在Linux下修改编码
- UIActivityIndicatorView 的使用
- 《Linux内核设计与实现》Chapter 2 读书笔记
- MVC ---- 标准查询运算符
- [CEOI2017]Building Bridges
- Effective STL 43: Prefer algorithm calls to hand-written loops
- 解决API中无法使用session问题
- .net core i上 K8S(七).netcore程序的服务发现
- php防止用户输入进行跨站攻击的方式