二分无敌~No.100 ACer

叉积判相交(左右手螺旋)

不相交 用解析式求四个点各自到另一条线段的垂线与其交点

前提是交点在线段上

ANS=MIN{两两之距,垂点之距}

用int64 才能过

有一个点10000

用叉积判断相交

用点积判断点到线段的垂线是否与线段相交

注意到,若两直线不相交

这个距离肯定是某端点 到另外线段的距离

二分求距离？数学方法不行吗？

暴力二分

function mindis(x,y:extended):extended;

var t:array[1..4]of extended;

midx,midy:extended;

begin

t:=line[2];

while abs(t[1]-t[3])+abs(t[2]-t[4])>1E-5 do

begin

midx:=(t[1]+t[3])/2;

midy:=(t[2]+t[4])/2;

if getdis(t[1],t[2],x,y)1E-5 do

begin

midx:=(line[1,1]+line[1,3])/2;

midy:=(line[1,2]+line[1,4])/2;

if mindis(line[1,1],line[1,2])

叉积判交叉，二分求距离！

若两线段平行，它们的距离不一定是垂线段的长度。。

把比赛时的程序删掉一段交上去就A了,狂冷...当时真是晕了.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

"相交就输出0.0000"

错的吧！！

我无语了。。

当时用解析几何搞了半死。。结果发现仅仅是判断是否相交和输出端点连线最小就70了。。。就算计算点线距没写也能在比赛的时候拿170（第四题轻松ac） 30min名次就20+了。。亏啊。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

偶的4.4k的程序~~T.T

比赛时，此题居然让我骗了90分

地板

90分,郁闷....

第一个AC~计算几何~

比赛的时候没有交啊啊啊啊啊啊

By Javran...