Cow Curling

İnek Curling'i 

İnek Curling'i, Moolympics'te yer alan popüler bir soğuk hava sporudur.

Normal Curling'deki gibi İnek Curling'i de 2 takım ile oynanır. Her takımın N(3 <= N <= 50,000) adet ağır taşı vardır ve bunları bir buz şeridi üzerinde kaydırarak bu oyun oynanır. Oyunun sonunda buzun üzerinde her biri farklı konumda olan 2N adet taş bulunur.

İnek Curling'inde skor olayı normal curlinge göre biraz farklıdır. Eğer bir taş rakip takımın taşları üçgenin köşeleri olacak şekilde herhangi bir üçgenin içerisindeyse o taş ele geçirilmiştir (Eğer taş üçgenin kenarlarından birinin üzerindeyse o da ele geçirilmiş sayılır). Bir takımın skoru karşı takımın ele geçirilmiş taş sayısına eşittir.

Sizden istenen 2N adet taşın hepsinin final durumları verildiğinde, maç skorunu bulmanız.

SORU İSMİ : curling

INPUT FORMAT:

* 1. satır: N sayısı.

* Satır 2..1+N: Her bir satır A'nın bir taşının x ve y koordinatlarını belirten iki tam sayıdan oluşuyor.(her bir koordinat [-40,000 , +40,000] aralığındadır).

* Satır 2+N..1+2N: Her bir satır B'nin bir taşının x ve y koordinatlarını belirten iki tam sayıdan oluşuyor. (her bir koordinat [-40,000 , +40,000] aralığındadır).

ÖRNEK INPUT (file curling.in):

4

0 0

0 2

2 0

2 2

1 1

1 10

-10 3

10 3

INPUT Açıklama:

Her bir takımın 4 taşı var. A'nınkilerin konumları (0,0), (0,2), (2,0), and (2,2), ve B'ninkilerin konumları (1,1), (1,10), (-10,3), and (10,3).

OUTPUT FORMAT:

* 1. satır: A ve B takımlarının skorlarını veren boşlukla ayrılmış 2 sayı.

ÖRNEK OUTPUT (file curling.out):

1 2 

OUTPUT Açıklama:

A, B'nin (1,1)'deki taşını ele geçiriyor. B de A'nın (0,2) ve (2,2)'deki taşlarını ele geçiriyor. Yani A'nın skoru 1, B'ninki 2. 

______________________________________________________________________

ÇÖZÜM:

Çözümde sadece, kaç tane mavi noktanın kırmızı noktalar tarafından oluşturulan üçgenler içerisinde yer aldığını nasıl bulacağımızı anlatacağız.Çünkü kaç kırmızının mavi üçgenler içerisinde yer aldığını da aynı yöntemle bulabiliriz.

Herhangi bir mavi nokta, kırmızı noktalardan oluşturulan herhangi bir üçgenin içerisindeyse, o nokta maviler tarafından “ele geçirilmiş” oluyor. O zaman burdan şunu da çıkarabiliriz:

Bir mavi nokta kırmızı noktalardan oluşan üçgenlerin birleşiminin oluşturduğu alanın içerisindeyse o nokta “ele geçirilmiş” tir. Üçgenlerin birleşimi üzerine biraz düşündüğümüz zaman üçgenlerin birleşiminin N tane kırmızı noktanın “Convex Hull”'ı olduğunu görüyoruz. “Convex Hull” 'ı herhangi bir O(N(log N))'lik algoritmayla bulabiliriz.

O zaman sorumuz şu hale geliyor:

N tane noktanın bu konveks alanın içerisinde olup olmadığını nasıl anlayabiliriz? Bu soruyu da konveks üzerindeki noktaları dairesel ya da soldan sağa sırayla tutarak çözebiliriz.

Önce dairesel şekilde tutarsak nasıl yapacağımıza bakalım.

Convex hull'ın içerisinde rastgele bir O noktası seçelim ve O noktasını orjin kabul edip, tüm noktaların koordinatlarını buna göre güncelleyelim. Bunu yaparak “Convex Hull” ' ımızın orjini içeridiğini garantilemiş olduk. Yani, “Convex Hull”'ın üzerindeki noktalar x ekseniyle yaptıkları açılara göre artan şekilde kolayca sıralanabilir hale geldi. Böylece, verilen herhangi bir mavi nokta için önce o noktanın x ekseniyle yapmış olduğu açıyı buluruz, sonra da konveksin o noktayla ilgili kenarını bulup sadece o kenarın solunda olup olmadığına bakarak noktanın konveksin içinde mi dışında mı olduğunu anlarız. (x ekseniyle yapmış olduğu açı bulunan nokta ile ilgili olan kenar binary search ile log(N)'de bulunabilir.)

Gelelim soldan sağa tutarsak nasıl yapacağımıza.

Konveks üzerindeki tüm noktaları x eksenlerine göre sıralayarak yamuklara ayırıyoruz. Her bir yamuk x değerlerine göre birbirinden farklı aralıkları kapsıyor. Böylece her bir nokta için ilgili yamuğu bulup içinde olup olmadığını kontrol ediyoruz.

İki durumda da O(log N) 'de herhangi bir noktanın kendisiyle ilgili kenar ya da yamuğa göre konumunu bulabiliyoruz. Bunu da N defa yapacağımızdan O(N log N)' de soruyu çözmüş oluyoruz.

Soruya burdan http://www.usaco.org/index.php?page=viewproblem2&cpid=382

Çözümün ingilizcesine ve çözüm koduna burdan http://www.usaco.org/current/data/sol_curling.html

Girdi-Çıktılara burdan http://www.usaco.org/current/data/curling.zip

ulaşabilirsiniz.