Mein vielleicht etwas naiver Ansatz (aber das sinnvollste, was mir nach 10 Min dazu eingefallen ist):
Du könntest deine Rechtecke in konzentrische Kreise um den Ursprung einbetten.
Skizze:
Dann könntest du deine Rechtecke evtl. in deiner Datenstruktur auch noch nach dem Radius ihres größtens sie noch berührenden Kreises anordnen. Die Euklid-Norm deines Punktes als Vektor aufgefasst kannst du ganz leicht berechnen; das musst du überdies auch nur einmal machen, denn die ändert sich ja während eines Durchlaufs nicht.
Anschließend kannst du die Rechtecke finden, die für einen Vergleich überhaut infrage kommen. Wenn du ein großes Feld mit vergleichsweise kleinen Rechtecken hast, dann werden das von vornherein nicht sehr viele sein.
Je nachdem wie geschickt du diese sortiert hast kannst du die ganz schnell finden und zum prüfen musst du auch nur den kleinen und großen Radius mit der Norm des Vektors vergleichen.
Wenn dann die Menge deiner Kandidaten schon so eingeschränkt ist kannst du für jedes dieser infrage kommenden Rechtecke einen "echten" Vergleich anstellen, ob dein Punkt nun drin liegt, oder nicht.