CTSC day2 杀菌计划

考场没能写出来。。我非常的不爽>_<。。。

于是我又写了一下。。
我首先阅读了空间几何的书籍。。进行了系统的学习。

当时我只知道空间中平面的表达式是A*x+B*y+C*z+D = 0。

那么使用解析流。。还是能应付题目中所需要的计算的。

但是。。解析流非常恶心。。。导致我写的时间巨长最后还因为一个小bug爆掉20分。
不过解析流有一个好处是可以直接写个gauss消元来搞。那么只要贴方程就行了
空间几何小贴士:

平面有两种表达法,解析式和点法式,

一个平面上的点p1和平面的法向量n决定一个平面。

平面上任意点必然满足(p-p1).dot(n) = 0。。

因为向量p-p1必然与n垂直,dot表示点积。

使用点法式之后。。适当使用点积和叉积。。就能轻松的应对题目中需要的各种计算了。。
我最后写了12KB。。。不过跑的还比较快,所有点都能在几秒内跑出来。。
计算多边形并的时候,使用最暴力的枚举所有关键x点,暴力计算即可。

投影到2维的时候,令d1 = (p2-p1)/(|p2-p1|),d2 = n.det(d1)。。
那么d1和d2就是平面上的一组垂直的单位向量,对于平面上的某点p,p-p1必然可以表示为x*d1+y*d2,

令x=(p-p1).dot(d1) , y = (p-p1).dot(d2)即可。
这样就投影完毕了。

剩下的工作都比较简单,使劲写就行了。

14 thoughts on “CTSC day2 杀菌计划

  1. Pingback: 一个逗比题目——CTSC day2 杀菌计划 | 日立君驻幻想乡隙间

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>