1263 -- Reflections

  简单计算几何。题目给出射线以及若干个不相交的圆,求出射线会在哪些圆上反弹,依次写出反弹球的编号。

代码如下:

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector> using namespace std; const double EPS = 1e-;
template<class T> T sqr(T x) { return x * x;}
inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
bool operator < (Point a) const { return sgn(x - a.x) < || sgn(x - a.x) == && y < a.y;}
bool operator == (Point a) const { return sgn(x - a.x) == && sgn(y - a.y) == ;}
Point operator + (Point a) { return Point(x + a.x, y + a.y);}
Point operator - (Point a) { return Point(x - a.x, y - a.y);}
Point operator * (double p) { return Point(x * p, y * p);}
Point operator / (double p) { return Point(x / p, y / p);}
} ;
typedef Point Vec; inline double cross(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
inline double cross(Point o, Point a, Point b) { return cross(a - o, b - o);}
inline double dot(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
inline double dot(Point o, Point a, Point b) { return dot(a - o, b - o);}
inline double veclen(Vec x) { return sqrt(dot(x, x));}
inline Vec normal(Vec x) { return Vec(-x.y, x.x) / veclen(x);} struct Line {
Point s, t;
Line() {}
Line(Point s, Point t) : s(s), t(t) {}
Vec vec() { return t - s;}
Point pt(double x) { return s + vec() * x;}
Line move(double x) {
Vec nor = normal(vec());
return Line(s + nor * x, t + nor * x);
}
} ; inline Point llint(Point P, Vec v, Point Q, Vec w) { return P + v * (cross(w, P - Q) / cross(v, w));}
inline Point llint(Line a, Line b) { return llint(a.s, a.vec(), b.s, b.vec());} struct Circle {
Point c;
double r;
Circle() {}
Circle(Point c, double r) : c(c), r(r) {}
} ; void lcint(Line L, Circle C, vector<Point> &sol) {
Point ip = llint(L, Line(C.c, C.c + normal(L.vec())));
double dis = veclen(ip - C.c);
if (sgn(dis - C.r) >= ) return ;
Vec u = L.vec() / veclen(L.vec());
double d = sqrt(sqr(C.r) - sqr(dis));
sol.push_back(ip + u * d);
sol.push_back(ip - u * d);
} Point reflect(Point x, Line L) {
Vec nor = normal(L.vec());
Point ip = llint(L, Line(x, x + nor));
return ip + ip - x;
} vector<Circle> rec;
Point src;
Vec dir; const double FINF = 1e100;
inline bool onCircle(Point p, Circle c) { return sgn(veclen(p - c.c) - c.r) == ;} void work() {
int cnt = , sz = rec.size();
vector<Point> tmp;
Point ip;
while (true) {
tmp.clear();
double d = FINF;
for (int i = ; i < sz; i++) lcint(Line(src, src + dir), rec[i], tmp);
for (int i = , sz = tmp.size(); i < sz; i++) {
double t = (tmp[i].x - src.x) / dir.x;
if (t > EPS) d = min(d, t);
}
if (sgn(d - FINF) >= ) break;
cnt++;
if (cnt > ) break;
ip = src + dir * d;
int mk = -;
for (int i = ; i < sz; i++) if (onCircle(ip, rec[i])) { mk = i; break;}
if (mk == -) { puts("shit!!"); while () ;}
printf("%d ", mk + );
dir = reflect(src, Line(ip, rec[mk].c)) - ip;
src = ip;
}
if (cnt > ) puts("...");
else puts("inf");
} int main() {
// freopen("in", "r", stdin);
int cas = , n;
double x, y, r;
while (cin >> n && n) {
rec.clear();
while (n--) {
cin >> x >> y >> r;
rec.push_back(Circle(Point(x, y), r));
}
cin >> src.x >> src.y;
cin >> dir.x >> dir.y;
dir = dir / veclen(dir);
printf("Scene %d\n", cas++);
work();
puts("");
}
return ;
}

  速度好慢,整整写了一个小时。对几何模板还是不算非常熟悉,虽然已经能够灵活写出部分基础函数了,但是速度还真是一个大问题。最后结果,因为手多血多个换行PE了一次,然后就AC了~

——written by Lyon

最新文章

  1. ipad pro 文章
  2. poj3070 (斐波那契,矩阵快速幂)
  3. linux shell 脚本获取和替换文件中特定内容
  4. js获取当前页面信息
  5. Event --mysql的scheduler.md
  6. SQL SERVER 中的 object_id()函数
  7. 在Nginx 下运行 Laravel5.1 的配置
  8. 分布式数据库中间件TDDL、Amoeba、Cobar、MyCAT架构比较分
  9. C语言嵌入式系统编程修炼之六:性能优化
  10. FlexGrid简单demo
  11. C++模板--实现容器适配器
  12. 利用angular给节点添加样式
  13. 封装好的MD5加密
  14. UML系列图
  15. 开源电子商务平台:OfBiz
  16. 测试系统工程师TSE需要具备的四项能力
  17. 解读经典《C#高级编程》第七版 Page50-68.核心C#.Chapter2
  18. 12.scrapy框架之递归解析和post请求
  19. TF常用知识
  20. 安装activemq和java代码实现生产和消费

热门文章

  1. JSP-JSP
  2. Springboot 创建的maven获取resource资源下的文件的两种方式
  3. Bnd教程(1):如何用命令行安装bnd
  4. 【JZOJ4896】【NOIP2016提高A组集训第16场11.15】兔子
  5. PHPCMS快速建站系列
  6. Linux常用命令1 文件处理命令
  7. iphone开发中使用nib(xib)文件的内存管理
  8. VIM中空格和TAB的替换
  9. AtCoder Beginner Contest 084 C - Special Trains
  10. Unity3D 物体旋转之Quaternion.Slerp