tag:blogger.com,1999:blog-1386177603599127652024-03-05T04:11:31.663-08:00চড়ুই এর ব্লগআনা ফারিহাhttp://www.blogger.com/profile/12218044748607197012noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-138617760359912765.post-61001837918566330662012-05-04T10:19:00.001-07:002012-05-04T13:23:04.352-07:00সার্কেল ইউনিয়ন<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBdmc15sdFMr6pFjIRUW-AX397-1dBp4RICA8oP1LAnsPoVfba86jFGEHptrzmQ8Er6j3qetdUa5jPyYKNXusLB2wTqc19kpAVv3q38fRa3_3LXCW2MpwJbuBIe7dmVVhbxvq5aiXNRdw/s1600/p2895.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br /></a></div>
<div style="text-align: justify;">
ধর তোমাকে বলা হল একটা চারকোনা টেবিল আছে, সাদা রংয়ের। এর মাঝে তুমি অনেকগুলা সিডি রাখতে পারো, ইচ্ছা মতো। আমরা ধরে নিচ্ছি টেবিলটা একটা ইনফাইনাইট প্লেন। তবে এই সিডিগুলা একটু বিশেষ ধরনের সিডি, এটা পুরা গোল চাকতির মতো, মানে সোজা কথায় এরা হল একটা করে ফিলড সার্কেল, যার মাঝখানে কোনো ফুটো নেই! এখন তুমি ইচ্ছা মতো সিডি রাখলে, একটার উপর আরেকটা, কোনো কোনোটা হয়তো পার্শিয়ালি ওভারল্যাপ করছে আরেকটার সাথে, ঠিক নিচের ছবিটার মতো। আমরা এখানে ধরে নিচ্ছি যে সিডিগুলোর উচ্চতা বলতে কিছুই নেই, মানে আমাদের ডিসকাশনে সব কিছুই টুডি।</div>
<br />
<br />
<div style="text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBdmc15sdFMr6pFjIRUW-AX397-1dBp4RICA8oP1LAnsPoVfba86jFGEHptrzmQ8Er6j3qetdUa5jPyYKNXusLB2wTqc19kpAVv3q38fRa3_3LXCW2MpwJbuBIe7dmVVhbxvq5aiXNRdw/s1600/p2895.jpg" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="263" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiBdmc15sdFMr6pFjIRUW-AX397-1dBp4RICA8oP1LAnsPoVfba86jFGEHptrzmQ8Er6j3qetdUa5jPyYKNXusLB2wTqc19kpAVv3q38fRa3_3LXCW2MpwJbuBIe7dmVVhbxvq5aiXNRdw/s320/p2895.jpg" width="320" /></a></div>
<div style="text-align: center;">
(এই ছবিটা ইউভিএ ১২০৫৬ থেকে নেয়া। প্রবলেম এর লিঙ্ক <a href="http://uva.onlinejudge.org/external/120/12056.html">এখানে</a>।)</div>
<br />
এখন তোমাকে সিডিগুলার সেন্টার (center) আর রেডিয়াস (radius) বলে দেয়া হল। এরপর যদি বলা হয় সিডিগুলোর কারণে, টেবিল এর কতটুকু এরিয়া দেখা যাচ্ছে না, তখন তুমি সেটা কিভাবে বের করবে? <br />
<br />
হুমম, চিন্তার বিষয়! তোমার নিশ্চয়ই মনে হচ্ছে এত গুলো সিডি দেয়ার কী দরকার ছিলো? দুই তিনটা দিলে ঠিকই বের করা যেত! আসলে দুই তিনটার জন্যে জেনারালাইজড সল্যুশন বের করতে পারলে মনে হয় অনেকগুলা সিডির জন্যেও পারা যাবে! চেষ্টা করে দেখা যাক। এখানে কোনো কোড দিব না, শুধু বেসিক আইডিয়াটা বলবো। আর সেটা থাকলেই তোমরা কোড করে নিতে পারবে। আর এই প্রবলেমটাকেই আমরা বলি <span style="color: #660000;">সার্কেল ইউনিয়ন</span> অথবা <span style="color: #660000;">এরিয়া অফ</span> <span style="color: #660000;">ইউনিয়ন অব সার্কেল</span> (Combined area of overlapping circles)। <br />
<br />
এই প্রবলেমের জন্যে প্রথমেই আমাদেরকে কিছু বিন্দু কে বেশী গুরুত্ব দিতে হবে। তিন ধরনের বিন্দুকে আমি বেশী গুরুত্ব দিব।<br />
<br />
১) প্রত্যেকটা বৃত্তের <b>leftmost</b> বিন্দু ( center.x - radius)।<br />
২) প্রত্যেকটা বৃত্তের <b>rightmost </b>বিন্দু ( center.x + radius)।<br />
৩) যে কোনো দুইটা বৃত্তের ছেদবিন্দু (intersection points between two circles)।<br />
<br />
<h3 style="text-align: left;">
<u><b><span style="font-weight: normal;">টুকরা টুকরা টুকরা</span></b></u></h3>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9vw9ZvjKjvSFZp0naYbyZ2RQVFQ3Mr_LzSR0FGTuleZW_UlG36Pd-2o_q9jVjotQOdMfzOzuJhTXHhgrWef5uN3FO_srEXMzT1QGY7C-Ou3o3w2JBymKhhphOD48087ssJPdFQnykkOo/s1600/1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9vw9ZvjKjvSFZp0naYbyZ2RQVFQ3Mr_LzSR0FGTuleZW_UlG36Pd-2o_q9jVjotQOdMfzOzuJhTXHhgrWef5uN3FO_srEXMzT1QGY7C-Ou3o3w2JBymKhhphOD48087ssJPdFQnykkOo/s1600/1.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
(এখানে তিনটা বৃত্তের জন্যে দেখানো হল)</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div style="text-align: left;">
আমরা গুরুত্বপূর্ণ বিন্দুগুলো পেয়ে গেছি! এখন আমরা যে কাজটা করবো তার নাম হল টুকরা টুকরা করা! সুন্দর ভাষায় বলতে গেলে স্লাইসিং (slicing)। ছবিটা দেখেই নিশ্চয়ই বুঝতে পারছো যে স্লাইসিং মানে কী? আমরা আমাদের ইন্টারেস্টিং পয়েন্টগুলিতে একটা করে লম্বা সরলরেখা একে বৃত্ত গুলোকে কতগুলো ডিসজয়েন্ট এলাকায় ভাগ করতে চাচ্ছি।</div>
<div style="text-align: left;">
<br /></div>
<h3 style="text-align: left;">
<u><b><u><b><span style="font-weight: normal;">রাঙিয়ে দাও আমার সবটাকে</span></b></u></b></u></h3>
<div style="text-align: left;">
<b><b><span style="font-weight: normal;">ভাগাভাগির কাজ তো শেষ</span></b></b>। এখন আলাদা জায়গাগুলোকে আলাদা রং দিলে কেমন হয়?</div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgsrRDvdoR2xd6H0e7pN_bpdVA5C5-EzOJhtVBWkuQdKXfdXldVuH4QHbLiI7nsAVLTpK3XJFtTVCN7AkA0YFH8CWzl31tRVtH7fWSdCTuLJZs059E6ZAFvcrkUsNE12uA66F1ETpmLrew/s1600/3+-+Copy+%282%29.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1-qZtrGCN298N-I5pEXQgug35o5XS71eJIb6FeArazB0FiAfYP5bMYJEkHQZQMNXzJ0YSZi2O8bdKWiATCdesiqQhVkVG00eDHAqZLgyilkrilLGTn-C7fUx26-Hqu1cA7rB9-mMw6hk/s1600/2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1-qZtrGCN298N-I5pEXQgug35o5XS71eJIb6FeArazB0FiAfYP5bMYJEkHQZQMNXzJ0YSZi2O8bdKWiATCdesiqQhVkVG00eDHAqZLgyilkrilLGTn-C7fUx26-Hqu1cA7rB9-mMw6hk/s1600/2.png" /></a></div>
<div style="text-align: justify;">
রং দিয়ে দিলাম, সবগুলো জায়গাকে। এখন বেশ পরিচ্ছন্ন মনে হচ্ছে জায়গা গুলোকে, আগের মতো তালগোল পাকানো মনে হচ্ছে না! কী বলো? এখন দেখে কী একটু একটু মনে হচ্ছে যে এরিয়াটা কোনভাবে বের করে ফেলা যাবে? সবথেকে মজার ব্যাপার হল, বৃত্তের সংখ্যা যত বেশীই হোক না কেন, এভাবে তুমি সব সময়ই সুন্দর সুন্দর রঙিন টুকরা করে ফেলতে পারবে, যারা প্রত্যেকেই হবে নিচের ছবিগুলোর যেকোন একটার মত।<br />
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh871s9oIU0KwF1JU4q7FKEtlIxWcescnlDPm3M9F17KrS9v08u2Ku8vowaCP457-moW2zxqRVdteSddgotu0-de7hkceV6tJY2TTtx7cb3OelhEgfv4dQwwANuoDotIjVcxPteQy7SxmY/s1600/3.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh871s9oIU0KwF1JU4q7FKEtlIxWcescnlDPm3M9F17KrS9v08u2Ku8vowaCP457-moW2zxqRVdteSddgotu0-de7hkceV6tJY2TTtx7cb3OelhEgfv4dQwwANuoDotIjVcxPteQy7SxmY/s200/3.png" width="155" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEge7Ga1aOBlXjTLAAma24cEiV6bH0Kvz2chLWJTvemFuTwToBaeUfe2U12IkwU4XHAh1tcEPAwXwxRkysgDUu5H8oFC3izh9UJ-XhRwoQWlV4zHDELbCfNY3N0_K4ZWSUEabW2DNiqFH98/s1600/3+-+Copy+%282%29.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="161" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEge7Ga1aOBlXjTLAAma24cEiV6bH0Kvz2chLWJTvemFuTwToBaeUfe2U12IkwU4XHAh1tcEPAwXwxRkysgDUu5H8oFC3izh9UJ-XhRwoQWlV4zHDELbCfNY3N0_K4ZWSUEabW2DNiqFH98/s200/3+-+Copy+%282%29.png" width="200" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgEuecihek34HYv87RO6jFO7zi9gG3TnQifWdKgSlwTiWH7hL1uqpZRo4WNa8o6SbBGlQBh_BRLf4kkwuoWMS5XlsgVYp9oeQSoH5OyCxnI8yayG1WITKSWnnMlP6t61LEv32itz1qs5HE/s1600/3+-+Copy.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgEuecihek34HYv87RO6jFO7zi9gG3TnQifWdKgSlwTiWH7hL1uqpZRo4WNa8o6SbBGlQBh_BRLf4kkwuoWMS5XlsgVYp9oeQSoH5OyCxnI8yayG1WITKSWnnMlP6t61LEv32itz1qs5HE/s200/3+-+Copy.png" width="134" /></a></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<u><b><u><b><u><b><u><b><span style="font-weight: normal;">শেষের শুরু</span></b></u></b></u></b></u></b></u></div>
<br />
<div style="text-align: left;">
এখন আসলে বাকি কাজটুকু সিম্পল জিওমেট্রি।</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
বামদিকের ছবিটার জন্যে, p1, p2, p3, p4 জানলে আর বৃত্তদুইটার কেন্দ্র আর ব্যাসার্ধ জানলে খুব সহজেই এরিয়াটা বের করে ফেলা যাবে। এরিয়াটা হবে:</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: center;">
<b><span style="color: #38761d;">সবুজ </span></b>p1p2p3p4 ট্রাপিজিয়ামের ক্ষেত্রফল + <b><span style="color: blue;">নীল </span></b>উপরের বৃত্তাংশটুকুর ক্ষেত্রফল + <b><span style="color: #bf9000;">হলুদ </span></b>নীচের বৃত্তাংশটুকুর ক্ষেত্রফল</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<span style="font-weight: normal;">মাঝখানের ছবিটার জন্যে বামদিকের ছবিটার ক্ষেত্রে যা করেছিলে সেইটা যতগুলি এনক্লোজিং এরিয়া আছে ততবার বের করতে হবে</span>। কিন্তু আমরা নিশ্চিত যে এই মাঝখানের গোলাপী এরিয়াগুলি কখনই একে অন্যকে ছেদ করবে না, মানে এই এরিয়াগুলো নিজেদের মাঝে ডিসজয়েন্ট! কারণ আমরা টুকরা করার সময় এই ব্যাপারটা নিশ্চিত করেই এগিয়েছি।</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
একদম শেষের, ডানদিকের ছবিটা বামদিকের ছবিটারই একটা স্পেশাল কেস, যেখানে উপরের আর নিচের চাপদুটি একই বৃত্তের অংশ। এটাও খুব সহজেই বের করে ফেলা সম্ভব।</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
এভাবে সবগুলো ভাগের জন্যে আলাদা আলাদা করে এরিয়া বের করে ফেলতে পারলেই তুমি গোটা এরিয়াটা বের করে ফেলতে পারবে, কারণ এই এরিয়াগুলো একটা আরেকটা কে কোনো ভাবেই ওভারল্যাপ করবে না । </div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
তো হয়ে গেলো আমাদের সার্কেল ইউনিয়ন এর কাজ। এখন তুমি সহজেই এরকম ক্ষেত্রে এরিয়াটা বের করে ফেলতে পারবে।</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<u>বি দ্র: এরপরের পোস্টে আমি কোড + কম্প্লেক্সিটি এনালাইসিস দেয়ার চেষ্টা করবো, তার আগে তোমরা আইডিয়াটা নিজে বুঝে কোড করার চেষ্টা করো আর আমাকে জানাও কোথাও কোনো সমস্যা থাকলে। ইউভিএ ১২০৫৬ দিয়েই শুরু করো না!</u></div>
<div style="text-align: left;">
<br /></div>
হ্যাপী কোডিং!</div>আনা ফারিহাhttp://www.blogger.com/profile/12218044748607197012noreply@blogger.com13