خوب و خرسی

۴ مطلب در مهر ۱۳۹۴ ثبت شده است

Pick's Theorem states that if we have a polygon with lattice points as vertices, then:

A = I + B/2 - 1

where A is the area of the polygon, I is the number of lattice points inside of the polygon, and B is the number of lattice points on the boundary of the polygon. We are asked to find I.

Thus, if we find A and B, w can use Pick's Theorem to find I. The area is simply M * P / 2. We can find B by noting that the number of points that lie on a line with lattice endpoints (W,X) and (Y,Z) is 1 + gcd(|Y - W|, |Z - X|). We find the number of boundary points on each edge of the triangle, and subtract 3 (because we are double counting the vertices of the triangle) to find B. 

موافقین ۰ مخالفین ۰ ۲۹ مهر ۹۴ ، ۱۳:۰۷
kherci

جهت فکرت رو عوض کن! به جای محور x  ها رو محور y ها حرکت کن!


یه عدد خیلی کوچیک:  1e-6

موافقین ۰ مخالفین ۰ ۲۹ مهر ۹۴ ، ۱۲:۵۶
kherci

1- memory limit ممکنه به خاطر از آرایه بیرون افتادن باشه!!

2- جهت فکرتو بچرخون

3- دنبال راه حلای ساده بگرد ساده ساده ساده...

4- فک کنم یه سوالی که خوبه اول حل سوال آدم از خودش بپرسه اینه : DP نداره؟! :| ea

موافقین ۰ مخالفین ۰ ۲۷ مهر ۹۴ ، ۰۸:۰۸
kherci

1- بعضی مسیرا اصلا وجود ندارن و باید فاصله شون بی نهایت می شده ولی صفر بوده!

2-  کامپیوتر کارا رو انجام میده تو اینقد فکر نکن! دنبال راه حلای ساده بگرد

3- به ورودی های مساله توجه کن بعضی وقتا سایز کم آرایه ها الگوریتمو مشخص می کنه!

+ divide it into steps 

موافقین ۰ مخالفین ۰ ۲۵ مهر ۹۴ ، ۱۰:۱۴
kherci