• ## Distance

千次阅读 2018-04-22 18:42:45
1191: Distance时间限制: 1 Sec 内存限制: 32 MB题目描述There is a battle field. It is a square with the side length 100 miles, and unfortunately we have two comrades who get hurt still in the battle ...
1191: Distance时间限制: 1 Sec  内存限制: 32 MB题目描述There is a battle field. It is a square with the side length 100 miles, and unfortunately we have two comrades who get hurt still in the battle field. They are in different positions. You have to save them. Now I give you the positions of them, and you should choose a straight way and drive a car to get them. Of course you should cross the battle field, since it is dangerous, you want to leave it as quickly as you can!输入There are many test cases. Each test case contains four floating number, indicating the two comrades' positions (x1,y1), (x2,y2).Proceed to the end of file.输出you should output the mileage which you drive in the battle field. The result should be accurate up to 2 decimals.样例输入1.0 2.0 3.0 4.0
15.0 23.0 46.5 7.0样例输出140.01
67.61提示The battle field is a square local at (0,0),(0,100),(100,0),(100,100).解题思路首先计算两点所确定的直线l，算出直线方程。计算出直线在x=0上的截距a和在x=100上的截距b，通过比较他们与0和100的关系可确定直线所处的位置，进而可利用勾股定理求出l在正方形内部的长度。#include <stdio.h>
#include <math.h>
int main()
{
double x1, x2, y1, y2, x, y, s, k, a, b;
while (~scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2))
{
if (x1 == x2 || y1 == y2)
{
printf("100.00\n");
continue;
}
k = (y1 - y2) / (x1 - x2);                          /*算出直线的斜率*/
a = y1 - k * x1;                                    /*算出直线在直线x=0上的截距a*/
b = y1 - k * (x1 - 100);                            /*算出直线在直线x=100上的截距b*/
if (a >= 100)
{
if (b < 0)
{
x = x1 - (y1 - 100) / k;
y = (x1 - y1 / k) - x;
s = sqrt(10000 + y * y);
printf("%.2f\n", s);
}
else if (b < 100)
{
x = 100 - (x1 - (y1 - 100) / k);
y = 100 - b;
s = sqrt(x * x + y * y);
printf("%.2f\n", s);
}
else printf("0.00\n");
}
else if (a >= 0)
{
if (b >= 100)
{
x = x1 - (y1 - 100) / k;
y = 100 - a;
s = sqrt(x * x + y * y);
printf("%.2f\n", s);
}
else if (b >= 0)
{
x = 100;
y = fabs(a - b);
s = sqrt(x * x + y * y);
printf("%.2f\n", s);
}
else
{
x = x1 - y1 / k;
y = a;
s = sqrt(x * x + y * y);
printf("%.2f\n", s);
}
}
else
{
if (b >= 100)
{
x = x1 - (y1 - 100) / k;
y = x - (x1 - y1 / k);
s = sqrt(10000 + y * y);
printf("%.2f\n", s);
}
else if (b > 0)
{
x = 100 - (x1 - y1 / k);
y = b;
s = sqrt(x * x + y * y);
printf("%.2f\n", s);
}
else printf("0.00\n");
}
}
return 0;
}
展开全文
• # quote from 'introduction to computation and programming # using Python, revised, MIT press import pylab def minkowskiDist(v1, v2, p): """Assumes v1 and v2 are equal-length arrays of numbe
# quote from 'introduction to computation and programming
# using Python, revised, MIT press
import pylab

def minkowskiDist(v1, v2, p):
"""Assumes v1 and v2 are equal-length arrays of numbers
Returns Minkowski distance of order p between v1 and v2"""
dist = 0.0
for i in range(len(v1)):
dist += abs(v1[i] - v2[i])**p
return dist**(1.0/p)

class Animal(object):
def __init__(self, name, features):
"""Assumes name a string; features a list of numbers"""
self.name = name
self.features = pylab.array(features)

def getName(self):
return self.name

def getFeatures(self):
return self.features

def distance(self, other):
"""Assumes other an animal
Returns the Euclidean distance between feature vectors
of self and other"""
return minkowskiDist(self.getFeatures(),
other.getFeatures(), 2)

def compareAnimals(animals, precision):
"""Assumes animals is a list of animals, precision an int >= 0
Builds a table of Euclidean distance between each animal"""
#Get labels for columns and rows
columnLabels = []
for a in animals:
columnLabels.append(a.getName())
rowLabels = columnLabels[:]
tableVals = []
#Get distances between pairs of animals
#For each row
for a1 in animals:
row = []
#For each column
for a2 in animals:
if a1 == a2:
row.append('--')
else:
distance = a1.distance(a2)
row.append(str(round(distance, precision)))
tableVals.append(row)
#Produce table
table = pylab.table(rowLabels = rowLabels,
colLabels = columnLabels,
cellText = tableVals,
cellLoc = 'center',
loc = 'center',
colWidths = [0.2]*len(animals))
table.scale(1, 2.5)
pylab.axis('off') #Don't display x and y-axes
pylab.savefig('distances')

rattlesnake = Animal('rattlesnake', [1,1,1,1,0])
boa = Animal('boa\nconstrictor', [0,1,0,1,0])
dartFrog = Animal('dart frog', [1,0,1,0,5])
alligator = Animal('alligator', [1,1,0,1,4])
animals = [rattlesnake, boa, dartFrog, alligator]
compareAnimals(animals, 3)
展开全文
• (From wikipedia) For binary strings a and b the Hamming distance is equal to the number of ones in a XOR b. For calculating Hamming distance between two strings a and b, they must have equal length. ...
• Given a tree, calculate the average distance between two vertices in the tree. For example, the average distance between two vertices in the following tree is (d01 + d02 + d03 + d04 + d12 +d13 +d14 +...
• The conic coordinates of a point p lying on the surface of the cone are two numbers: the first, d, is the distance from the tip of the cone to p and the second, A , is the angle in degrees between ...
• Find the farthest distance Bessie can get from the farm and still make it back in time. Input * Line 1: Five space-separated integers: M, T, U, F, and D * Lines 2..T+1: Line i+1 describes path segment...
• If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L ) where D1 and D2 are as distant from each other as possible ...
• If the grid is aligned such that the grid lines are parallel to the x- and y-coordinate axes, the distance one needs to walk or drive from one point to the other, assuming you can only move along ...
• Given a tree, calculate the average distance between two vertices in the tree. For example, the average distance between two vertices in the following tree is (d01 + d02 + d03 + d04 + d12 +d13 +d14 +...
• <div><p>Keeping on with the basics <p><img alt="distance_point_plane_sverchok_blender_project_on_plane" src=...<p><img alt="distance_point_plane_sverchok_blender_project_on_plane" src=...
• String Distance is a non-negative integer that measures the distance between two strings. Here we give the definition. A transform list is a list of string, where each string, except for the last one,...
• <div><p>The manual describes Hausdorff distance as follows: <p>.. method:: object.hausdorff_distance(other) <p>Returns the Hausdorff distance (<code>float) to the <code>other</code> geometric object....
• The K-th Distance Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 27 Accepted Submission(s): 5 Problem Description Given a tree, which has n ...
• ## 编辑距离算法（Edit Distance）

万次阅读 多人点赞 2016-12-31 21:31:35
写在前面的话今年是2016年的最后一天，外公，超级想你，我都没有想过你会不能继续再走到2017.我过得很好，每天都超级幸福，我现在在学校有一堆好朋友。哈哈，我总是能处在宇宙中心的那种人，没办法，您这么优秀才能...
写在前面的话
今年是2016年的最后一天，外公，超级想你，我都没有想过你会不能继续再走到2017.我过得很好，每天都超级幸福，我现在在学校有一堆好朋友。哈哈，我总是能处在宇宙中心的那种人，没办法，您这么优秀才能教出这么好的孙女，好吧。
我会好好学习的，我是第一女王嘛，永远都会是的。是吧，要做就做最好，要么就不做，我永远都要做你的骄傲。对了，我又有很多新朋友了，我们就像家人一样，就是每天都过得超级幸福，哈哈，就是有种魔力，能让我遇到的人都把像家人一样对待。我又变美了，好吧，简直是全院最美的，好吧。现在有一堆人在照顾我，保护我，给我开心，带我给无穷无尽的快乐，我从来都没有这么开心过。生命真的很奇特，不是么。
啊，对了，隆达罗西复出了，我们等了好久，你在天国要记得看知道么。还有啊，要照顾好自己。我爱你哟，你知道超级爱～
好像这个月写的都是传说中的"情感"博客，看不下去了，出来写篇非情感博客。
好像我的技术博客情感博客变成了主线，技术博客变成了背景衬托，哈哈哈，心疼的抱抱订阅我博客的小伙伴们。
感觉最近打字真的很顺溜啊。哟西，速度真的是杠杠滴
终于可以不正紧的写一篇技术博客了，画风突然有点奇特，嘎嘎嘎～

概念
编辑距离的作用主要是用来比较两个字符串的相似度的
基本的定义如下所示：
编辑距离，又称Levenshtein距离（莱文斯坦距离也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
在概念中，我们可以看出一些重点那就是，编辑操作只有三种。插入，删除，替换这三种操作，我们有两个字符串，将其中一个字符串经过上面的这三种操作之后，得到两个完全相同的字符串付出的代价是什么就是我们要讨论和计算的。
例如：
我们有两个字符串： kitten 和 sitting:
现在我们要将kitten转换成sitting
我们可以做如下的一些操作；
k i t t e n --> s i t t e n  将K替换成S
sitten --> sittin 将 e 替换成i
sittin --> sitting  添加g
在这里我们设置每经过一次编辑，也就是变化（插入，删除，替换）我们花费的代价都是1。
例如：

如果str1=“ivan”，str2=“ivan”，那么经过计算后等于 0。没有经过转换。相似度=1-0/Math.Max(str1.length,str2.length)=1

如果str1=“ivan1”，str2=“ivan2”，那么经过计算后等于1。str1的"1"转换"2"，转换了一个字符，所以距离是1，相似度=1-1/Math.Max(str1.length,str2.length)=0.8

#算法过程

1.str1或str2的长度为0返回另一个字符串的长度。 if(str1.length0) return str2.length; if(str2.length0) return str1.length;

2.初始化(n+1)(m+1)的矩阵d，并让第一行和列的值从0开始增长。扫描两字符串（nm级的），如果：str1[i] == str2[j]，用temp记录它，为0。否则temp记为1。然后在矩阵d[i,j]赋于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。

3.扫描完后，返回矩阵的最后一个值d[n][m]即是它们的距离。

计算相似度公式：1-它们的距离/两个字符串长度的最大值。

其实这个算法并不难实现
我们用字符串“ivan1”和“ivan2”举例来看看矩阵中值的状况：
1、第一行和第一列的值从0开始增长

图一
首先我们先创建一个矩阵，或者说是我们的二维数列，假设有两个字符串，我们的字符串的长度分别是m和n，那么，我们矩阵的维度就应该是(m+1)*(n+1).
注意，我们先给数列的第一行第一列赋值，从0开始递增赋值。我们就得到了图一的这个样子
之后我们计算第一列，第二列，依次类推，算完整个矩阵。
我们的计算规则就是：
d[i,j]=min(d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp) 这三个当中的最小值。
其中：str1[i] == str2[j]，用temp记录它，为0。否则temp记为1
我们用d[i-1,j]+1表示增加操作
d[i,j-1]+1 表示我们的删除操作
d[i-1,j-1]+temp表示我们的替换操作
2、举证元素的产生 Matrix[i - 1, j] + 1 ; Matrix[i, j - 1] + 1   ;    Matrix[i - 1, j - 1] + t 三者当中的最小值

3.依次类推直到矩阵全部生成

这个就得到了我们的整个完整的矩阵。
下面我们来看下代码，我最擅长的就是Python，下面我们来看实现：
#!/usr/bin/env python
# coding=utf-8
# function   : calculate the minEditDistance of two strings
# author     : Chicho
# date       : 2016-12-31

def minEditDist(sm,sn):
m,n = len(sm)+1,len(sn)+1

# create a matrix (m*n)

matrix = [[0]*n for i in range(m)]

matrix[0][0]=0
for i in range(1,m):
matrix[i][0] = matrix[i-1][0] + 1

for j in range(1,n):
matrix[0][j] = matrix[0][j-1]+1

for i in range(m):
print matrix[i]

print "********************"

cost = 0

for i in range(1,m):
for j in range(1,n):
if sm[i-1]==sn[j-1]:
cost = 0
else:
cost = 1

matrix[i][j]=min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+cost)

for i in range(m):
print matrix[i]

return matrix[m-1][n-1]

mindist=minEditDist("ivan1","ivan2")
print mindist

我们来看下最后得到的运行结果：

上面是一个初始化的矩阵

最后得到的结果，距离就是最后右下角的那个值1
下面我们在根据计算出两个字符串的相似度：
最后得到它们的距离=1
相似度：1-1/Math.Max(“ivan1”.length,“ivan2”.length) =0.8

参考文献：
http://www.cnblogs.com/ivanyb/archive/2011/11/25/2263356.html
写在后面的话
无意中发现了一个巨牛的人工智能教程，忍不住分享一下给大家。教程不仅是零基础，通俗易懂，而且非常风趣幽默，像看小说一样！觉得太牛了，所以分享给大家。点这里可以跳转到教程 https://www.cbedai.net/chichoxian

外公，爱你，给你一个敲大的么么哒

希望生命可以产生所有奇妙的化学反应


展开全文
• Given a tree, calculate the average distance between two vertices in the tree. For example, the average distance between two vertices in the following tree is (d01 + d02 + d03 + d04 + d12 +d13 +d14 +...
• <p>The geodesic distance returns inf in many cases. So I was running my experiments and I found that on many occasions the geodesic distance returns inf which makes the distance_to_goal measurement in...
• - (Alternatively) Change any of the View Distance options for the player while in-game and notice the view distance update to the appropriate distance <p><strong>Where did the issue occur? - Editor ...
• <div><p>Right now, collision checks using SceneGraph ...<p>We should offer a version of <code>ComputeSignedDistancePairwiseClosestPoints()</code> that takes an influence distance parameter such as <code>...
• <p>I'm having problems with st_distance function in postgis. It returns wrongs results - for small distances the error isn't big - 10, maybe 20 meters but for bigger distances the difference between ...
• <div><p>Is there any way to get a distance field with this project? The distance filter works but it doesn't seem to return what the actual distance is. I can do something like qs.annotate...
• <div><p>I attempted to compute the signed distance between two spheres, using a diagram containing an MBP and a SceneGraph. Calling <code>ComputeSignedDistancePairwiseClosestPoints()</code> repeatedly...
• <div><p>I would like to see a new 3D Home Distance variable in iNav. It could be used in the OSD and with Logic Conditions. <p>It would combine distance from home with absolute altitude (negative ...
• What it actually do, is replaced most checks, which involves distance measurement to check is actor closer/further than some specific distance, to use distance squared instead which increase ...
• ## LeetCode Edit Distance

千次阅读 2014-12-31 14:42:12
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)You have the following 3 operations permitted on a ...
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)You have the following 3 operations permitted on a word:a) Insert a characterb) Delete a characterc) Replace a character思路分析：经典dp问题，可以定义二维数组dp[word1.length + 1][word2.length + 1], dp[i][j]表示word1前i个字符（i可以为0）到word2前j个字符（j也可以为0）的编辑距离。那么递推方程可以写成dp[i][j]=dp[i-1][j-1] if word1[i-1]=word2[j-1];  dp[i][j]=min{dp[i-1][j-1], dp[i][j-1], dp[i-1][j]} + 1 if word1[i-1]!=word2[j-1]详细解释可以参考 http://fisherlei.blogspot.com/2012/12/leetcode-edit-distance.htmlAC Codepublic class Solution {
public int minDistance(String word1, String word2) {
int l1 = word1.length();
int l2 = word2.length();
int [][] dp = new int[l1+1][l2+1];

for(int i = 0; i <= l1; i++){
dp[i][0] = i;
}

for(int j = 0; j <= l2; j++){
dp[0][j] = j;
}

for(int i = 1; i <= l1; i++){
for(int j = 1; j <= l2; j++){
if(word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
}
}
}
return dp[l1][l2];
}
}
展开全文
• <div><p>We need the ability to query the signed-distance field from each sphere in each frame to all objects in a specific frame. We assume all query spheres locate within a user-defined bounding box....
• int hammingDistance(int x, int y) { int xa[20], ya[20]; for (int i = 0; i; i++) { if (x)break; else { xa[i] = x % 2; x = x / 2; ya[i] = y % 2; y = y / 2; ...
• <p>I've done a bit of reading on this but there's hardly any information on doing it using points and the st_distance function in mysql. I suppose this makes sense since according to ...
• Py之distancedistance的简介、安装、使用方法之详细攻略 目录 distance的简介 distance的安装 distance的使用方法 1、编辑距离、汉明距离、sorensen相似系数、jaccard系数、ifast_comp distance的...

...