ტყვეები ომიდან

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2002/03, DEC, GREEN


2002 წლის ხარების აჯანყების შემდეგ ძროხებს უამრავი ტყვის თვალყურის პრობლემა  გაუჩნდათ. მათ გააჩნიათ საპყრობილე კოორდინატებით  (Px, Py)     (სადაც -100,000 <= Px <= 100,000 და -100,000 <= Py <= 100,000).   მის  გარშემო  ისინი  აპირებენ მრავალი  ღობის აშენებას  რომ  მაქსიმალურად  გამორიცხონ  გაპარვის   შემთხვევები. ამ  მიზნით  ძროხებმა  ციხის  მახლობლად  განალაგეს  N  (3 <= N <= 1000)  პოსტი. ყოველი  ღობე შეიცავს  ციხეს და მის შიგნით განლაგებულ ღობეებს. ღობეები ერთმანეთს არ კვეთენ. ციხე და პოსტები წერტილების სახით რომ წარმოვიდგინოთ,  მათგან  არც ერთი სამეული არ მდებარეობს ერთ  წრფეზე  (არ არიან კოლინეარული).  მოცემული პოსტების განლაგებების თანახმად ააგეთ მაქსიმალური რაოდენობით ერთმანეთში ჩადებული შეკრული ღობეები ისე რომ ღობეების მონაკვეთების ბოლოები პოსტებს წარმოადგენდნენ.  ღობეებს შორის და აგრეთვე ციხესა და ყველაზე შიდა ღობეს შორის მცველებს პატრულირება უნდა შეეძლოთ ( წიბოს მეშვეობით არ შეაერთოთ ერთმანეთს ჩადებული ღობეები).

შესატანო მონაცემები

* სტრიქონი 1: შეიცავს სამ ჰარით დაშორებულ მთელს N, Px,  და Py.

* სტრიქონები  2..N+1: ორი მთელი Xi და Yi (-100000 <= Xi, Yi <= 100000) - პოსტების კოორდინატები.

 

გამოსატანი მონაცემები:  

ერთი სტრიქონი ერთი მთელი რიცხვით: ჩადებული ღობეების მაქსიმალური რაოდენობა.

 

 




მაგალითები

შესატანი მონაცემები
8 -1 0 2 2 2 -2 -2 2 -2 -2 0 10 8 0 -12 1 1 -5 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება