algorithm - CLRS:33.1-4:Show how to determine in O(n*n*lg n) time whether any three points in a set of n points are colinear? -

-

i going through clrs book of algorithms computational geometry. in exercise of 33.1-4 has asked "show how determine in o(n*n*lg n) time whether 3 points in set of n points colinear?" can done in o(n*n*n) time complexity taking 3 point @ time , doing cross product, not able understand how can in o(n*n*lg n) time. need help.

let slope(p, q), 2 points p , q, slope of line passing through p , q. now, 3 points, p, q , r, collinear iff slope(p,q) = slope(p,r). thus, fixing p, can determine in o(n*log n) time if there 2 other points q , r such pqr line. done compute slope(p,q) other points q in set of n points, , checking if there repetitions - use set-like structure or sort , check duplicates. now, iterate on choices p, giving runtime of o(n*n*log n).


Comments

Post a Comment

Popular posts from this blog

java - Plugin org.apache.maven.plugins:maven-install-plugin:2.4 or one of its dependencies could not be resolved -

-
i getting error message , further 1 here: failed read artifact descriptor org.apache.maven.plugins:maven-install-plugin:jar:2.4: even though when go .m2 repository path c:\users\a591024.m2\repository\org\apache\maven\plugins\maven-resources-plugin\2.4 the maven-resources-plugin-2.4.jar file there , maven-resources-plugin-2.4.pom there. have tried delete .m2 repository no luck. far maven not build project desperately need to. any ideas? it seems proxy issue please aad following in setting.xml grabbing lan setting , proxy information. <proxies> <proxy> <id>proxy</id> <active>true</active> <protocol>http</protocol> <host>hostname</host> <port>port</port> </proxy> </proxies> this frequent issue, please see below link well. plugin org.apache.maven.plugins:maven-clean-plugin:2.5 or 1 of dependencies not resolved maven: failed ret...
Read more

Round ImageView Android -

-
Image
i working on android application in doing rounded image view. working fine images, images 160x120 resolution shows oval shaped. code custom imageview given below, please me out here: public class roundimage extends drawable { private final bitmap mbitmap; private final paint mpaint; private final rectf mrectf; private final int mbitmapwidth; private final int mbitmapheight; public roundimage(bitmap bitmap) { mbitmap = bitmap; mrectf = new rectf(); mpaint = new paint(); mpaint.setantialias(true); mpaint.setdither(true); final bitmapshader shader = new bitmapshader(bitmap, shader.tilemode.clamp, shader.tilemode.clamp); mpaint.setshader(shader); mbitmapwidth = mbitmap.getwidth(); mbitmapheight = mbitmap.getheight(); } @override public void draw(canvas canvas) { canvas.drawoval(mrectf, mpaint); } @override protected void onboundschange(rect bound...
Read more

How can I utilize Yahoo Weather API in android -

-
Image
i want develop app using yahoo weather api android. want current , forecast weather details. i have tried different sources (e.g.: https://github.com/survivingwithandroid/weatherlib , getting error weatherlib api android , unable execute activity in android weatherlib ) , getting different errors m unable resplve. there can proper tutorial or guide! error: -17 08:50:48.961 3168-3168/com.survivingwithandroid.weather e/androidruntime﹕ fatal exception: main process: com.survivingwithandroid.weather, pid: 3168 java.lang.runtimeexception: unable start activity componentinfo{com.survivingwithandroid.weather/com.survivingwithandroid.weather.mainactivity}: java.lang.nullpointerexception: attempt invoke interface method 'boolean java.util.list.isempty()' on null object reference @ android.app.activitythread.performlaunchactivity(activitythread.java:2298) @ android.app.activitythread.handlelaunchactivity(activitythread.java:2360) @ android.app.activi...
Read more