hdu3712 Detector Placement
2024-08-31 06:45:45
题意：给一束激光，一个三棱柱，三棱柱会折射光，问这束激光最终是否会和y = 0相交；
分析：模拟题，为了方便处理折射角，事先求出每条边的向内和向外的法向量；
findpoint : 找第一交点
step1: 判断激光是否和三角形有规范相交；
step2: 第一次折射；
step3:第二次折射，可能无法折射；
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N = +;
const double eps = 1e-;
const double pi = acos(-1.0);
inline int dcmp(double x) {
return x < -eps ? - : x > eps;
}
inline double sqr(double x) {
return x * x;
} struct Point{
double x,y;
Point(){}
Point(double _x,double _y):x(_x),y(_y){}
bool operator == (const Point &p) const{
return dcmp(x - p.x) == && dcmp(y - p.y) == ;
}
Point operator + (const Point &p) const{
return Point(x + p.x, y + p.y);
}
Point operator - (const Point &p) const{
return Point (x - p.x, y - p.y);
}
Point operator * (const double &k) const{
return Point (x * k, y * k);
}
Point operator / (const double &k) const{
return Point (x / k, y / k);
}
double operator * (const Point &p) const{
return x * p.y - y * p.x;
}
double operator / (const Point &p) const{
return x * p.x + y * p.y;
}
double len2() {
return x * x + y * y;
}
double len() {
return sqrt(len2());
}
Point scale(const double &k) {
return dcmp( len() ) ? (*this) * (k / len()) : (*this);
}
Point turnLeft() {
return Point(-y,x);
}
Point turnRight(){
return Point(y,-x);
}
double Distance(const Point &p) {
return sqrt(sqr(x - p.x) + sqr(y - p.y));
}
Point rotate(const Point &p,double angle, double k = ) {
Point vec = (*this) - p;
double c = cos(angle * k) , s =sin(angle * k) ;
return p + Point(vec.x * c - vec.y * s, vec.x * s + vec.y * c);
}
void input(){
scanf("%lf%lf",&x,&y);
}
void ot() {
printf("%.3lf %.3lf\n",x,y);
}
};
double Angle(Point a,Point b) {
return (a/b) / a.len() / b.len();
}
struct Line{
Point a,b;
Line(){}
Line(Point a,Point b):a(a),b(b){}
double operator * (const Point &p) const{
return (b - a) * (p - a);
}
double operator / (const Point &p) const{
return (p - a) / (p - b);
}
bool IsPointOnSeg(const Point &p) {
return dcmp( (a - p) * (b - p) ) == && dcmp( (p - a) / (p - b) ) <= ;
}
int LineCrossSeg(const Line &v) {//2jiao, 1 dian ,0 wu
int d1 = dcmp( (*this) * v.a), d2 = dcmp((*this) * v.b);
if ((d1 ^ d2) == -) return ;
return (d1 == || d2 == );
}
Point CrossPoint(const Line &v) {
double s1 = v * a, s2 = v * b;
return ( a * s2 - b * s1 ) / (s2 - s1);
}
};
Line li[];
int d[];
Point a[],b[],c[];
Point st,en; double u;
int check(int i) {
if (dcmp( (li[i].b - li[i].a) * (a[d[i]] - li[i].a) ) > ) {
return ;
}
return ;
}
void init(){
for (int i = ; i < ; i++) {
if (check(i)) {
b[i] = (li[i].b - li[i].a).turnLeft();
c[i] = (li[i].b - li[i].a).turnRight();
}else {
b[i] = (li[i].b - li[i].a).turnRight();
c[i] = (li[i].b - li[i].a).turnLeft();
}
}
}
int ond(Point a,Point b,Point p) {
if (dcmp((p - a) / (b - a)) >= ) return ;
return ;
}
int step1() {
int fg = ;
Line line = Line(st,en);
for (int i = ; i < ; i++) {
if (line.LineCrossSeg(li[i]) == ) {
Point p = line.CrossPoint(li[i]);
if (ond(st,en,p)) fg = ;
}
}
if (fg == ) { Point p = line.CrossPoint(Line(Point(,),Point(,)));
if (ond(st,en,p)) printf("%.3lf\n",p.x+eps);
else printf("Error\n");
return ;
}
return ; }
void findPoint(Point &p,int &id) {
Line line = Line(st,en);
double dis = 1e50;
for (int i = ; i < ; i++) {
if (line.LineCrossSeg(li[i])) {
Point tp = line.CrossPoint(li[i]);
if (!ond(st,en,tp)) continue;
double tdis = tp.Distance(st);
if (tdis < dis && dcmp(tdis) != ) {
dis = tdis;
p = tp;
id = i;
}
}
}
}
void step2() {
Point p;
int id = -;
findPoint(p,id);
Point vec = en - st;
double cs = Angle(vec,b[id]);
double sn1 = sqrt( - cs * cs);
double sn2 = sn1 / u;
double ag = asin(sn1) - asin(sn2);
if (dcmp(vec * b[id]) <= ) {
vec = (p + vec).rotate(p,-ag);
}else vec = (p + vec).rotate(p,ag);
st = p; en = vec;
}
void step3() {
Point p;
int id = -;
findPoint(p,id);
Point vec = en - st;
double cs = Angle(vec,c[id]);
double sn1 = sqrt( - cs * cs);
double sn2 = sn1 * u;
if (sn2 > ) {
if (dcmp(p.y) == ) printf("%.3lf\n",p.x+eps);
else printf("Error\n");
return;
}
double ag = asin(sn2) - asin(sn1);
if (dcmp(vec * c[id]) >= ) {
vec = (p + vec).rotate(p,-ag);
}else vec = (p + vec).rotate(p,ag);
st = p; en = vec;
Point an = Line(st,en).CrossPoint(Line(Point(,),Point(,)));
if (ond(st,en,an)) {
printf("%.3lf\n",an.x+eps);
}else printf("Error\n");
}
void solve(){
init();
if (!step1()) return;
step2();
step3();
}
int main(){
// cout<<Line(Point(0,0),Point(1,0)).LineCrossSeg(Line(Point(0,0),Point(1,0)))<<endl;
int T; scanf("%d",&T);
while (T--) {
st.input(); en.input();
for (int i = ; i < ; i++) a[i].input();
li[] = Line(a[],a[]); d[] = ;
li[] = Line(a[],a[]); d[] = ;
li[] = Line(a[],a[]); d[] = ;
scanf("%lf",&u);
solve();
}
return ;
}
/*
3
0 10
0 20
-1 3 1 2 -1 1
1.325
0 10
0 0
-1 3 1 2 -1 1
1.325 0 10 0 9
0 0 0 1 1 0
1.0
*/
最新文章
- nginx服务器命令
- Entity Framework Linq 动态组合where条件
- OAF_开发系列17_实现OAF数组应用Vector / Hashmap / Hashtable / Arraylist（案例）
- Java Web 三层架构详解
- JavaScript parseInt函数
- (转)android图片压缩总结
- Smart Card Filesystem
- Linux Shell入门（转载）
- android改变字体的颜色的三种方法
- python学习笔记--导入tab键自动补全功能的配置
- html mysql special character
- node.js的安装及配置
- Imcash科普：没有网络也可以转账比特币？你可能有些误解
- Spring MVC的原理及配置详解
- 【Python】Xml To Excel
- Sublime Text快捷键与插件介绍
- VS2013软件的安装和单元测试
- 矩阵游戏 HYSBZ - 1059（最大流）
- HDU 1867 A + B for you again 字符匹配
- 基于JT/T808协议的车辆监控平台架构方案