http://poj.org/problem?id=1066

题目大意:给一个由墙围成的正方形,里面有若干墙,每次破墙只能从(当前看到的)墙的中点破,求最少破多少墙才能看到宝藏。

——————————————————————

显然枚举起点然后画一条以终点为端点的线,求线和多少墙相交即可。

但是我不会证明:这里有证明:https://www.cnblogs.com/anrainie/p/4049844.html

然后有该证明我们得到只要起点为这些线的端点即可。

#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double dl;
const int INF=;
const int N=;
struct point{//既是向量又是点
dl x;
dl y;
}p[*N],ed;
int n;
inline point getmag(point a,point b){
point s;
s.x=b.x-a.x;s.y=b.y-a.y;
return s;
}
inline dl multiX(point a,point b){
return a.x*b.y-b.x*a.y;
}
inline int intersect(point a,point b){
int ans=;
if(a.x==b.x&&a.y==b.y)return ;
for(int i=;i<=n;i++){
dl d1=multiX(getmag(a,p[i]),getmag(a,b))*multiX(getmag(a,p[i+n]),getmag(a,b));
dl d2=multiX(getmag(p[i],a),getmag(p[i],p[i+n]))*multiX(getmag(p[i],b),getmag(p[i],p[i+n]));
if(d1<=&&d2<=)ans++;
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y);
}
scanf("%lf%lf",&ed.x,&ed.y);
if(n==){
printf("Number of doors = 1\n");
return ;
}
int ans=INF;
for(int i=;i<=*n;i++){
ans=min(ans,intersect(p[i],ed));
}
printf("Number of doors = %d\n",ans);
return ;
}

最新文章

  1. Win7 64位 MinGW环境测试SDL2.0.3
  2. Java基础之网络编程
  3. mac:在当前文件夹打开terminal终端
  4. C# @Page指令中的AutoEventWireup,CodeBehind,Inherits
  5. Linux学习笔记总结--memcached配置
  6. c#基础语言编程-程序集和反射
  7. .NET架构师
  8. JVM基础(4)-编译
  9. 用anaconda的pip安装第三方python包的日志
  10. Android 串口设置校验位、速率、停止位等参数
  11. Spark算子--countByKey
  12. CSA Round #54 $\ $Voting
  13. springboot的maven配置问题
  14. python学习笔记----面向对象
  15. 什么是python的全局解释锁(GIL)
  16. python3 logging模块
  17. iOS Block初探
  18. CSS写的提示框(兼容火狐IE等各大浏览器)
  19. Asp.Net Core 轻松学-一行代码搞定文件上传 JSONHelper
  20. vue 阅读一【待完结】

热门文章

  1. Hive支持行级update、delete时遇到的问题
  2. Java+Selenium 3.x 实现Web自动化 - 1.自动化准备
  3. Cannot assign requested address (connect failed)
  4. Linux命令应用大词典-第30章 审计系统
  5. 初学Direct X(8) ——碰撞检测
  6. 【scroll-view】 可滚动视图组件说明
  7. Bootstrap栅格系统基本使用
  8. python数据分析基础——pandas Tutorial
  9. (转)CGMA - Organic World Building in UE4: week 6
  10. 【转】跨平台移动端开发框架NativeScript 发布正式版本