Foren » 36. BwInf

• Max Kamps

  

  • 2 Beiträge
   

  17. September 2017 17:06:26 CEST

  Hallo,
  
  Ich war gerade dabei, Aufgabe 3 zu lösen, als mir aufgefallen ist dass sich in beinahe allen Beispieldateien drei oder sogar vier Strecken in einem Punkt schneiden.
  
  Ausschnitt aus dreiecke5.txt:
  130 130 160 140
  160 140 190 0
  160 140 160 170
  
  Aber in der Aufgabenstellung steht
  "Du kannst davon ausgehen, [...] dass sich nie mehr als zwei Strecken im gleichen Punkt schneiden."
  
  MFG
  Max
• Thomas Leineweber

  

  • 230 Beiträge
   

  17. September 2017 21:56:03 CEST

  ja, hier haben drei Strecken einen Punkt gemeinsam (160 140). Aber dies ist jeweils ein Endpunkt der Strecke. Vermultich ist "schneiden" in dem Sinne gemeint, dass am Schnittpunkt die Strecke in zwei Teile mit einer Länge >0 geteilt wird.
• Wolfgang Pohl

  

  • Moderator
  • 391 Beiträge
   

  18. September 2017 10:16:14 CEST

  Genau. Die Einschränkung der Aufgabenstellung soll die Berechnung von Schnittpunkten erleichtern. Vorgegebene Endpunkte müssen aber nicht mehr berechnet werden.
• Max Kamps

  

  • 2 Beiträge
   

  18. September 2017 18:00:02 CEST

  Erstmal danke für die Antworten!
  
  Das ganze gibt mir jetzt aber schon zu denken, ob ich vielleicht doch einen sehr naiven Algorithms gewählt habe...
  
  Naja, mal sehen...
• Wolfgang Pohl

  

  • Moderator
  • 391 Beiträge
   

  29. September 2017 16:29:56 CEST

  Nachtrag zu diesem Thema: In der Eingabedatei dreiecke3.txt gab es wirklich einen Schnittpunkt, der mit einem Eckpunkt zusammenfällt. Hier ergeben sich dann doch Probleme. Wir haben dies Eingabe deshalb gegen eine neue ausgetauscht; siehe https://www.bwinf.de/bundeswettbewerb/der-36-bwinf/1-runde/material-361/.
  
  
• simon waidelich

  

  • 21 Beiträge
   

  3. Oktober 2017 14:36:36 CEST

  Hi,
  
  eigentlich verstehe ich diese Diskussion nicht. Ein einfacher Algorithmuss macht doch gar keinen Unterschied zwischen einem Schnittpunkt in der Mitte oder an den Enden der Strecke. Beides liegt AUF der Strecke.
  
  Weiterhin verstehe ich nicht warum es eine Vereinfachung darstellen soll, wenn sich nicht mehr als zwei Strecken in einem Punkt innerhalb und nicht am Rand schneiden dürfen. Für einen einfachen Algorithmuss stellen mehrfach Schnittpunkte keine Hürde dar. Eventuell sollte man sagen, dass ein Dreieck einen Flächeninhalt von >0 haben sollte??
  
  Simon
  Dieser Beitrag wurde am 3. Oktober 2017 14:37:53 CEST von simon waidelich bearbeitet
• Wolfgang Pohl

  

  • Moderator
  • 391 Beiträge
   

  6. Oktober 2017 14:58:34 CEST

  Schnittpunktberechnung geht in der Regel nur mit Gleitkommazahlen, und da kann es Ungenauigkeiten geben. Dann kann es vorkommen, dass aus einem Schnittpunkt dreier Strecken drei leicht unterschiedliche Schnittpunkte jeweils zweier Strecken werden. Und prompt hat man ein weiteres Dreieck, dessen Fläche durchaus >0 ist. Eine Fläche >e (e wie epsilon, und e>0) zu fordern, könnte aber helfen.
• simon waidelich

  

  • 21 Beiträge
   

  6. Oktober 2017 16:46:21 CEST

  Super, genau das habe ich gemeint! :) Wollte aber nichts verraten...gelle...