Vijos服务器,还要加油啊…
Posted by Javran on 07月 27th, 2008
参加了Vijos的比赛,不过由于服务器的问题,就交了一题,很迟才连上Vijos,题目等了半天,结果就做了两题.
第一题计算几何,还算拿手,点乘叉乘全用上了,还复习了一回数学知识
第四题,今天手感不错,几乎没有调试就过了样例,用TTPlayer的歌词做测试数据,效果很理想,甚至比我想的还好点
就交了这题了
顺便说一下我第一题的思路:
题目大意是给定线段AB,CD,求之间最短距离
首先分二种情况:
1.相交输出0.0000
2.不相交
相交的判断用跨立实验就可以了,比如检验AB与CD是否相交,就是检验CD是否分立于AB两端以及检验AB是否分立于CD两端,用向量叉积做跨立实验就好了
不相交的话..我是猜想的:
先取AC,AD,BC,BD最小值赋给ans
检验A到CD,B到CD,C到AB,D到AB的垂足的位置
如果在线段内就用相应距离尝试更新ans
检验时我用了点积,由于Cos=(AB.CD)/(|AB|*|CD|)
于是Cos和AB.CD的符号是一样的
检验时:
例如检验A到BC的垂线,其实只要检验∠ABC和∠ACB是否都不为钝角(Cos大于0)就可以了
那么距离呢?…再拿A到BC说,AB叉乘AC等于△ABC面积的两倍,除以BC取绝对值就行了,
不知道这么做是不是对的,反正我还没有交程序,以后有时间我试试看….
郁闷啊…………………………………………………
后续报道:
测试时只交一题,100分
另一题自己交上去测,190分
最后改了个地方,200分
两题能这么撑(虽然是水题)已经可以了
好了,提交的程序全部满分了,加个庆祝标签,今天到此为止.