[Codeforces 32E] Hide-and-Seek
2024-10-20 13:39:48
Brief Intro:
给两个人的坐标,一堵墙和一面镜子,询问两人能否看见对方
Solution:
一道以分类讨论为主的计算几何题,
分别讨论两人坐标连线是否经过墙/镜子即可,
难点在于如何求出点x关于线段[A,B]的对称点:
point sym(point x,point A,point B){return *dot(A,B)/dot(B,B)*B-A+x;}
以上给出一种方法:将线段[x,A]延长一倍,求出线段[x,x']的向量,再行加减即可
Code:
#include <bits/stdc++.h> using namespace std; typedef complex<double> point; point a,b,w1,w2,m1,m2; point read(){double x,y;cin>>x>>y;return point(x,y);}
double det(point a,point b){return imag(a*conj(b));}
double dot(point a,point b){return real(a*conj(b));}
bool on_seg(point x,point L,point R){return det(L-x,R-x)== && dot(L-x,R-x)<=;}
bool seg_cross(point a,point b,point c,point d)
{
double s1=det(c-a,b-a)*det(b-a,d-a);
double s2=det(a-c,d-c)*det(d-c,b-c);
if(s1< || s2<) return false;
if(s1== && s2==) return on_seg(c,a,b) || on_seg(d,a,b);
return true;
}
point sym(point x,point A,point B){return *dot(A,B)/dot(B,B)*B-A+x;} bool check()
{
if(seg_cross(a,b,m1,m2))
return !seg_cross(a,b,w1,w2) && det(b-a,m2-m1)==;
else if(seg_cross(a,b,w1,w2))
{
point A=sym(m1,a-m1,m2-m1),B=sym(m1,b-m1,m2-m1);
return (seg_cross(a,B,m1,m2) && !seg_cross(a,B,w1,w2) && !seg_cross(A,b,w1,w2));
}
return true;
} int main()
{
a=read();b=read();w1=read();w2=read();m1=read();m2=read(); cout << (check()?"YES":"NO");
return ;
}
Review:
1、求两线段是否有重合部分:
先判相交,再判叉积是否为0
2、判断一点是否在线段上:
先用叉积判是否在直线上,再用点积判线段两端是否在其两侧
最新文章
- [转]Android音频底层调试-基于tinyalsa
- ES6笔记(7)-- Promise异步编程
- 工作中常用的Linux命令:find命令
- linux 远程桌面连接
- 打包jar文件 外部调用资源 so等
- 利用反射及JDBC元数据编写通用查询方法
- TCP通讯socket自定义协议的实现
- Fence9
- 关于Collection&#39;
- JSP技术模型(五)JSP隐含变量
- HDU 5288 OO‘s sequence (技巧)
- Zabbix实战-简易教程(7)--监控第一台host
- 初始ajax技术
- TestNg框架基础入门
- 弹性(flex)布局
- IdentityServer4【Introduction】之术语
- NOIP2002-2017提高组题解
- opencv 基本使用
- java学习记录--ThreadLocal使用案例
- 【HDU】2866:Special Prime【数论】