დროის ლიმიტი: 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 დაკოპირება