ارث پدری(3امتیاز)

[lof]

پدری از دنیا رفت و زمینی به شکل مستطیل را که در آن 1000 درخت گردو به صورت پراکنده وجود داشت برای دو پسرش به ارث گذاشت. دو پسر تصمیم گرفتند زمین را با یک خط مستقیم طوری به دو بخش تقسیم کنند که در هر بخش دقیقا 500 درخت گردو وجود داشتته باشد. (مساحت زمین ها اهمیتی ندارد)

آیا این کار در هر صورت امکان پذیر است؟ در صورت مثبت بودن پاسخ روشی برای این کار ارائه دهید.

 

[Shadow!]

پاسخ : ارث پدری(3امتیاز)

زمینو نشون بده تا بهت بگم

 

[lof]

پاسخ : ارث پدری(3امتیاز)

===========================
| * * * * * * * * * * * * * * * * * * * * |
| * * * * * * * * * * * * * * * * * * * * |
| * * * * * * * * * * * * * * * * * * * * |
| * * * * * * * * * * * * * * * * * * * * |
| * * * * * * * * * * * * * * * * * * * * |
===========================

اینم زمین فقط درختا رو 10 برابر کن و این که صرفا مرتب نیستن هچل هفت ریختن به هم!

ببینم چه میکنی

 

[mahrud]

پاسخ : ارث پدری(3امتیاز)

از الگوریتم سوییپ لاین استفاده میکنیم: http://en.wikipedia.org/wiki/Sweep_line_algorithm
یه خط رندوم اون وسط بزار، فرض کن یه طرفش بیشتر از اون طرف درخت هست. اختلاف سمت چپ و راست رو بگیر D ، الان D مثبت هست.
این خط رو همین جوری حرکت بده تا وقتی که D منفی بشه. (البته این "همینجوری" بهتره هوشمندانه باشه!)
در این صورت اگر درخت ها زوج باشن، حتمن یه زمانی D صفر شده، پس دو طرف برابر شدن

 

[lof]

پاسخ : ارث پدری(3امتیاز)

از الگوریتم سوییپ لاین استفاده میکنیم: http://en.wikipedia.org/wiki/Sweep_line_algorithm
یه خط رندوم اون وسط بزار، فرض کن یه طرفش بیشتر از اون طرف درخت هست. اختلاف سمت چپ و راست رو بگیر D ، الان D مثبت هست.
این خط رو همین جوری حرکت بده تا وقتی که D منفی بشه. (البته این "همینجوری" بهتره هوشمندانه باشه!)
در این صورت اگر درخت ها زوج باشن، حتمن یه زمانی D صفر شده، پس دو طرف برابر شدن

ببین قسمت دومش رو درست گفتی ولی اولش:

اون خط رو ما چه جوری فرضش کنیم که با حرکت دادنش بعد یه مدتی 2 طرف یکسان باشن؟

 

[mahrud]

پاسخ : ارث پدری(3امتیاز)

مهم نیست! یه خط تصادفی انتخاب میکنیم (که گذرنده از هیچ درختی نباشه بدیهتن)، بعد هر دفعه یه جوری میچرخونیمش که دقیقن یک درخت از یک سمت بره به سمت دیگه، و ترجیحا طوری که D به صفر نزدیک تر بشه.
پ.ن: این نکته ی "دقیقن یک درخت از یک سمت بره به سمت دیگه" رو جا انداخته بودم، خیلی مهمه که پیوسته باشه. بهش میگن اصل مقدار میانی
راستی، ببخشید حواسم نبود، باید پیغام خصوصی میدادم؟ اگه میخوای حذف کن که لوس نشه برای بقیه. ببخشید واقعن

 

[lof]

پاسخ : ارث پدری(3امتیاز)

مهم نیست! یه خط تصادفی انتخاب میکنیم (که گذرنده از هیچ درختی نباشه بدیهتن)، بعد هر دفعه یه جوری میچرخونیمش که دقیقن یک درخت از یک سمت بره به سمت دیگه، و ترجیحا طوری که D به صفر نزدیک تر بشه.
پ.ن: این نکته ی "دقیقن یک درخت از یک سمت بره به سمت دیگه" رو جا انداخته بودم، خیلی مهمه که پیوسته باشه. بهش میگن اصل مقدار میانی
راستی، ببخشید حواسم نبود، باید پیغام خصوصی میدادم؟ اگه میخوای حذف کن که لوس نشه برای بقیه. ببخشید واقعن

ببین حرفتو نمیتونم بپذیرم باید خطو یه جوری در نظر بگیری که وقتی از یه سمت شروع به حرکت میدیش دقیقا بعد یه زمان 500 تا این ور باشه 500 تا اونور

این خطه باید یه ویژگی داشته باشه

ولی خیلی نزدیک شده! خیلی!

 

[HHH]

پاسخ : ارث پدری(3امتیاز)

هر درختیو یه مختصات می گیریم
اگر خط رو عدد گنگ بیفته حله دیگه

 

[lof]

پاسخ : ارث پدری(3امتیاز)

هر درختیو یه مختصات می گیریم
اگر خز رو عدد گنگ بیفته حله دیگه

نه ببینین خود درختا وضعیتشون نسبت به هم رو هم در نظر بگیرین

اینم راهنمایی

 

[HHH]

پاسخ : ارث پدری(3امتیاز)

خب یه جا که تراکم کمتر یا بین زیگزاگ درختا خطو می کشیم

 

[lof]

پاسخ : ارث پدری(3امتیاز)

خب یه جا که تراکم کمتر یا بین زیگزاگ درختا خطو می کشیم

از کجا میدونی که این زیگ زاگا اگه از بینشون خط راستی رسم شه به درختی نخوره؟!

نه

(خط باید راست بشه)

 

[mahrud]

پاسخ : ارث پدری(3امتیاز)

بزار اینجوری بگم، مرکز مستطیل رو در نظر بگیر، یه خط از اونجا رسم کن که به هیچ درختی نخوره. بعد همینجوری اون خطه رو بچرخون.
با برهان خلف، فرض کن اولش تفاوت سمت راست و چپ مثبت باشه، وقتی ۱۸۰ درجه چرخوندی هم مثبت باشه. که تناقضه. پس وقتی ۱۸۰ درجه چرخوندیم منفی شده، پس یه جا اون وسطا صفر شده.
این خوبه؟
فکر کنم باگ داشته باشه ..

 

[lof]

پاسخ : ارث پدری(3امتیاز)

بزار اینجوری بگم، مرکز مستطیل رو در نظر بگیر، یه خط از اونجا رسم کن که به هیچ درختی نخوره. بعد همینجوری اون خطه رو بچرخون.
با برهان خلف، فرض کن اولش تفاوت سمت راست و چپ مثبت باشه، وقتی ۱۸۰ درجه چرخوندی هم مثبت باشه. که تناقضه. پس وقتی ۱۸۰ درجه چرخوندیم منفی شده، پس یه جا اون وسطا صفر شده.
این خوبه؟

درسته ولی جواب اصلش رو اگه کسی تونس بگه به اونم میدم امتیازشو

فعلا با این روش تو 3امتیاز گرفتی

 

[HHH]

پاسخ : ارث پدری(3امتیاز)

خطی که از یه نقطه روی مستطیل رد بشه می کشیم بعد هول محور دوران میدیم هروقت به هیچ درختی نخورد خط رو به روشی که ماهرود گفت جابه جا می کنیم

×ویرایش: پست دیر رسید پاک کن


lof:نیاز به پاک نیست

 

[mahrud]

پاسخ : ارث پدری(3امتیاز)

فهمیدم باگشو. ممکنه موقع چرخوندن این خط، یهو یه درخت از سمت راست بره سمت چپ، یه درخت دیگه هم از اون طرف از سمت چپ بره سمت راست. یا مثلا اختلاف ۱ باشه، بعد دو تا درخت با هم از سمت راست برن سمت چپ، میشه منفی یک. ولی صفر نشده.
باید یه نقطه انتخاب کنیم که با هیچ دو درختی هم خط نباشه. حالا شد.

 

[lof]

پاسخ : ارث پدری(3امتیاز)

فهمیدم باگشو. ممکنه موقع چرخوندن این خط، یهو یه درخت از سمت راست بره سمت چپ، یه درخت دیگه هم از اون طرف از سمت چپ بره سمت راست. یا مثلا اختلاف ۱ باشه، بعد دو تا درخت با هم از سمت راست برن سمت چپ، میشه منفی یک. ولی صفر نشده.
باید یه نقطه انتخاب کنیم که با هیچ دو درختی هم خط نباشه. حالا شد.

در واقع باید خطی انتخاب کرد که با هیچ خطی که دو درخت رو به هم وصل میکنه موازی نباشه بعد از یه ور میریم یه طرف دیگه تا وقتی که بالاخره 500 تا اینور باشن 500 تا اونور

تقریبا درس گفتی

حل قفل