11 Ekim 2018

Euler Projesi 252. Soru

Konveks (İçbükey) Delikler

Verilen bir noktalar kümesi için bu noktaları köşe kabul eden ve herhangi diğer noktayı içine almayan herhangi bir çokgene bir konveks delik adı verilir (noktalar çokgenin kenarı üzerinde bulunabilir). 

Örneğin aşağıdaki resimde 20 nokta kümesi ve birkaç böylesi konveks delik gösteriliyor. Kırmızı çizgilerle gösterilen yedigen şekilli konveks delik 1049694,5 birim kare alana sahip olup verilen noktalar kümesi için olası en büyük alana sahip konveks deliktir.

Verilen örnek için aşağıdaki pseudo-random sayı üreteciyle üretilen ilk 20 $(T_{2k-1},T_{2k})$ noktası kullanılmıştır: $$S_0=290797 \\ S_{n+1}={S_n}^2 \, mod\, 50515093 \\ T_n=(S_n \, mod \, 2000)-1000$$yani (527,144), (-488,732), (-454, -947) gibi.

Pseudo-random sayı üretecindeki ilk 500 noktanın oluşturduğu kümede bir konveks delik için olası en büyük alan kaçtır?

Cevabınızı bir ondalık basamak olacak şekilde veriniz.
Cevap: 104924.0