POJ1066:Treasure Hunt——题解
2024-10-21 13:07:33
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 ;
}
最新文章
- Win7 64位 MinGW环境测试SDL2.0.3
- Java基础之网络编程
- mac:在当前文件夹打开terminal终端
- C# @Page指令中的AutoEventWireup,CodeBehind,Inherits
- Linux学习笔记总结--memcached配置
- c#基础语言编程-程序集和反射
- .NET架构师
- JVM基础(4)-编译
- 用anaconda的pip安装第三方python包的日志
- Android 串口设置校验位、速率、停止位等参数
- Spark算子--countByKey
- CSA Round #54 $\ $Voting
- springboot的maven配置问题
- python学习笔记----面向对象
- 什么是python的全局解释锁(GIL)
- python3 logging模块
- iOS Block初探
- CSS写的提示框(兼容火狐IE等各大浏览器)
- Asp.Net Core 轻松学-一行代码搞定文件上传 JSONHelper
- vue 阅读一【待完结】
热门文章
- Hive支持行级update、delete时遇到的问题
- Java+Selenium 3.x 实现Web自动化 - 1.自动化准备
- Cannot assign requested address (connect failed)
- Linux命令应用大词典-第30章 审计系统
- 初学Direct X(8) ——碰撞检测
- 【scroll-view】 可滚动视图组件说明
- Bootstrap栅格系统基本使用
- python数据分析基础——pandas Tutorial
- (转)CGMA - Organic World Building in UE4: week 6
- 【转】跨平台移动端开发框架NativeScript 发布正式版本