博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
算法教程(3)zz
阅读量:5874 次
发布时间:2019-06-19

本文共 5836 字,大约阅读时间需要 19 分钟。

First off, we can use our code to test for the "BOUNDARY" case. If the distance from any segment to the test point is 0, then return "BOUNDARY". If you didn't have that code pre-written, however, it would probably be easier to just check and see if the test point is between the minimum and maximum x and y values of the segment. Since all of the segments are vertical or horizontal, this is sufficient, and the more general code is not necessary.

Next we have to check if a point is in the interior or the exterior. Imagine picking a point in the interior and then drawing a ray from that point out to infinity in some direction. Each time the ray crossed the boundary of the polygon, it would cross from the interior to the exterior, or vice versa. Therefore, the test point is on the interior if, and only if, the ray crosses the boundary an odd number of times. In practice, we do not have to draw a raw all the way to infinity. Instead, we can just use a very long line segment from the test point to a point that is sufficiently far away. If you pick the far away point poorly, you will end up having to deal with cases where the long segment touches the boundary of the polygon where two edges meet, or runs parallel to an edge of a polygon — both of which are tricky cases to deal with. The quick and dirty way around this is to pick two large random numbers for the endpoint of the segment. While this might not be the most elegant solution to the problem, it works very well in practice. The chance of this segment intersecting anything but the interior of an edge are so small that you are almost guaranteed to get the right answer. If you are really concerned, you could pick a few different random points, and take the most common answer.

String testPoint(verts, x, y){    int N = lengthof(verts);    int cnt = 0;    double x2 = random()*1000+1000;    double y2 = random()*1000+1000;    for(int i = 0; i
Requires:
In problems like this, the first thing to figure out is what sort of solutions might work. In this case, we want to know what sort of circles we should consider. If a circle only has two points on it, then, in most cases, we can make a slightly smaller circle, that still has those two points on it. The only exception to this is when the two points are exactly opposite each other on the circle. Three points, on the other hand, uniquely define a circle, so if there are three points on the edge of a circle, we cannot make it slightly smaller, and still have all three of them on the circle. Therefore, we want to consider two different types of circles: those with two points exactly opposite each other, and those with three points on the circle. Finding the center of the first type of circle is trivial — it is simply halfway between the two points. For the other case, we can use the method for . Once we find the center of a potential circle, it is then trivial to find the minimum radius.
int[] x, y;int N;double best = 1e9;void check(double cx, double cy){    double max = 0;    for(int i = 0; i< N; i++){        max = max(max,dist(cx,cy,x[i],y[i]));    }    best = min(best,max);}double minRadius(int[] x, int[] y){    this.x = x;    this.y = y;    N = lengthof(x);    if(N==1)return 0;    for(int i = 0; i
Requires:
This problem actually requires an extension of the Line-Point Distance method discussed previously. It is the same basic principle, but the formula for the is a bit different in three dimensions.
The first step here is to convert from spherical coordinates into (x,y,z) triples, where the center of the earth is at the origin.
double x = sin(lng/180*PI)*cos(lat/180*PI)*alt;    double y = cos(lng/180*PI)*cos(lat/180*PI)*alt;    double z = sin(lat/180*PI)*alt;
Now, we want to take the cross product of two 3-D vectors. As I mentioned earlier, the cross product of two vectors is actually a vector, and this comes into play when working in three dimensions. Given vectors
(x1,y1,z1) and
(x2,y2,z2) the cross product is defined as the vector
(i,j,k) where
i = y1z2 - y2z1;    j = x2z1 - x1z2;    k = x1y2 - x2y1;
Notice that if z
1 = z
2 = 0, then i and j are 0, and k is equal to the cross product we used earlier. In three dimensions, the cross product is still related to the area of the parallelogram with two sides from the two vectors. In this case, the area of the parallelogram is the norm of the vector:
sqrt(i*i+j*j+k*k).
Hence, as before, we can determine the distance from a point (the center of the earth) to a line (the line from a satellite to a rocket). However, the closest point on the line segment between a satellite and a rocket may be one of the end points of the segment, not the closest point on the line. As before, we can use the dot product to check this. However, there is another way which is somewhat simpler to code. Say that you have two vectors originating at the origin, S and R, going to the satellite and the rocket, and that |X| represents the norm of a vector X.
Then, the closest point to the origin is R if
|R|2 + |R-S|2 ≤ |S|2 and it is S if
|S|2 + |R-S|2 ≤ |R|2
Naturally, this trick works in two dimensions also.
Further Problems
Once you think you've got a handle on the three problems above, you can give these ones a shot. You should be able to solve all of them with the methods I've outlined, and a little bit of cleverness. I've arranged them in what I believe to ascending order of difficulty.
Requires:
Requires:
Requires:
Requires: ,
Requires: ,
Requires: ,
Requires: ,
Requires: ,
Requires: ,
The following problems all require geometry, and the topics discussed in this article will be useful. However, they all require some additional skills. If you got stuck on them, the editorials are a good place to look for a bit of help. If you are still stuck, there has yet to be a problem related question on the that went unanswered.

转载地址:http://yfhnx.baihongyu.com/

你可能感兴趣的文章
神经网络的火热
查看>>
视图之一--创建简单的视图
查看>>
for循环实例
查看>>
N1试卷常考词汇总结
查看>>
构建之法阅读笔记(1)
查看>>
POJ 3663:Costume Party
查看>>
主机连接虚拟机 web服务
查看>>
ajaxSubmit的data属性
查看>>
NetStatusEvent info对象的状态或错误情况的属性
查看>>
linux命令学习
查看>>
Windows下第三方库安装Nuget与Vcpkg
查看>>
URL的截取问题
查看>>
My first post
查看>>
git分支
查看>>
Ehcache 缓存
查看>>
list删除重复元素
查看>>
绘制屏幕时给单选按钮分组
查看>>
TCP/IP协议、DoD模型、OSI模型
查看>>
java开发环境
查看>>
Can't create handler inside thread that has not called Looper.prepare()
查看>>