Labb 4Läs igenom labbinstruktionerna innan ni börjar. Tips: I speciellt C++ men även Java är det ganska praktiskt att använda iteratorer för att representera vektorer/mängder/etc. För mer detaljer se Labb 1. För alla uppgifter gäller att lösningen måste vara effektiv i fråga om tid och minne. I de fall uppgiften är att implementera en specifik algoritm går det bra att implementera en annan algoritm så länge den har samma eller bättre komplexitet. Observera att API-förslagen nedan är att betrakta som pseudo-kod. Ni måste översätta dem till ert favoritspråk på det sätt ni tycker verkar bäst. 4.1 PunktklassFör den här labben behöver du implementera en klass för att hantera 2-dimensionella punkter (vektorer). Klassen bör innehålla vanliga operationer på vektorer, t.ex.
4.2 PolygonerUppgift 4.2.1: beräkna arean av en enkel polygon(1p)Skriv en metod för att beräkna arean av en (enkel) polygon. Förslag till API: Rekommenderad tidskomplexitet: O(n). Problem-id hos Kattis: polygonarea. Uppgift 4.2.2: Punkt inuti polygon (1p)Skriv en metod för att avgöra om en punkt ligger inuti en (enkel) polygon. Förslag till API: Rekommenderad tidskomplexitet: O(n). Problem-id hos Kattis: pointinpolygon. 4.3 Linjer och linjesegmentUppgift 4.3.1: Skärningspunkt för linjesegment (1p)Skriv en metod som kan hitta skärningspunkten mellan två linjesegment. Metoden ska kunna identifiera om skärningen saknas, om skärningen är en punkt, eller om skärningen är ett helt linjesegment (d.v.s. om de två segmenten är parallella och överlappar). Förslag till API: Problem-id hos Kattis: segmentintersection. Uppgift 4.3.2: Avstånd mellan linjesegment (1p)Skriv en metod för att beräkna avståndet mellan två linjesegment (d.v.s. det kortaste avståndet mellan någon punkt i det ena segmentet och någon punkt i det andra segmentet) Förslag till API: Problem-id hos Kattis: segmentdistance. 4.4 PunktmängderUppgift 4.4.1: närmsta par av punkter - effektiv algoritm i genomsnitt (1p)Skriv en metod för att hitta ett par av punkter som ligger närmast varandra i en punktmängd. Metoden ska ha förväntad körtid O(n log n) under antagandet att indatapunkterna är likformigt fördelade i en delkvadrat av R2. Ni behöver inte kunna bevisa att er algoritm har den förväntade körtiden. Förslag till API: Problem-id hos Kattis: closestpair1. Uppgift 4.4.2: närmsta par av punkter - effektiv algoritm i värsta fall(1p)Skriv en metod för samma problem med värsta falls-körtid O(n log n). Problem-id hos Kattis: closestpair2. Uppgift 4.4.3: beräkna konvexa höljet (1p)Skriv en metod för att beräkna det konvexa höljet av en punktmängd. Metoden ska kunna hantera degenererade punktmängder (t.ex. att alla punkter ligger längs en linje). Metoden ska ha komplexitet O(n log n). Förslag till API: Problem-id hos Kattis: convexhull. Uppgift 4.4.4: beräkna antal kolinjära punkter (1p)Skriv en metod som givet en punktmängd hittar en maximal mängd kolinjära punkter (d.v.s. en mängd punkter som alla ligger längs samma räta linje). Det räcker att du hittar det maximala möjliga antalet punkter i en sådan mängd. Din metod bör ha väsentligt bättre komplexitet än Ω(n3). Förslag till API: Problem-id hos Kattis: maxcolinear. Uppgift 4.5: Linjära rekurrenserUppgift 4.5.1: Implementera beräkning av linjära rekurrenser (1p)Problem-id hos Kattis: linearrecurrence. |