আজকে আমরা আরেকটি প্রোগ্রামিং প্রবলেম নিয়ে আলোচনা করব । আমরা ইতোমধ্যে বিভিন্ন অনলাইন জাজ এর কিছু প্রবলেম নিয়ে আলোচনা করেছি । কম্পিউটার বিজ্ঞান এর একটি অত্যন্ত গুরুত্বপূর্ণ শাখা  হচ্ছে প্রোগ্রামিং প্রবলেম সমাধান । এতে আমাদের চিন্তার দক্ষতা যেমন বাড়ে , ঠিক তেমনিভাবে আমাদের একাডেমিক এবং জ্ঞানের পরিধি ও বাড়াতে এটি খুবই সহায়ক ।

তো প্রবলেম পাওয়ার জন্য অসংখ্য সাইট বা অনলাইন জাজ রয়েছে । এর মধ্যে খুবই পরিচিত একটি সাইট Uva Online Judge. আজকে আমরা এই সাইটের একটি প্রবলেম নিয়ে আলোচনা করব । আবার এই প্রবলেমটি আরেকটি অতি পরিচিত এবং খুবই জনপ্রিয় আরেকটি অনলাইন জাজ Light Oj এও দেয়া আছে ।

তো আমরা আর কথা না বাড়িয়ে আমাদের আলোচনা শুরু করি ।

প্রবলেম লিঙ্কঃ https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3835

http://lightoj.com/volume_showproblem.php?problem=1388&language=english&type=pdf

প্রবলেমটিতে বলা হয়েছে , আমাদের একটি ট্রাপিজিয়াম আঁকতে হবে ।যেখানে ট্রাপিজিয়াম এর বাহু AB এর A আর B এর কো-অর্ডিনেট দেয়া আছে । আর অবশিষ্ট ৩ বাহু b,c,d এর দৈর্ঘ্য দেয়া আছে । আমাদের প্রিন্ট করতে হবে C আর D পয়েন্ট এর কো-অর্ডিনেট । আর সবপয়েন্ট গুলো এমনভাবে আসতে হবে যাতে সেগুলো ঘড়ির কাঁটার বিপরীতদিকে বা anti – clockwise  অবস্থান করে ।

Algorithm :

আমাদের মূল কাজ আসলে খুবই সোজা । আমরা এখানে প্রথমে একটি পয়েন্ট  বের করব AB বাহুর অপর । মনে করি পয়েণ্টটি P . আমরা যদি CD এর সমান্তরাল করে AB এর একটি অংশ কেটে নিই তাহলে আমরা বলতে পারি AP  = a – c আর PB = c  । তাহলে আমরা এই হিসেবে P এর স্থানাংক পেয়ে যাবে । এখন আমরা DP  = b  বলতে পারি । আর আমরা জানি AD = d .  তাহলে আমরা এখন এই  দুইটি মানের অপর ভিত্তি করে সমীকরণ তৈরী করতে পারি । আর এই সমীকরণ সমাধান করে আমরা ২টি বিন্দু পাব । এর মধ্যে যে বিন্দুটি আমার AB  সাপেক্ষে ঘড়ির কাঁটার বিপরীতে অবস্থান করবে সেটিই হবে আমার D এর নির্ণেয় স্থানাংক । ঠিক একই ভাবে আমরা C এর স্থানাংক বের করব ।

আমরা ব্যাপারটিকে একটু ছবিতে দেখাই

untitled got

Equations :

  1. লাইন সমীকরণ : Ax + BY = C
  2. x এর মান বের করার সমীকরণ / দ্বিঘাত সমীকরণ : Dx^2 +Ex + F = 0 , (x = – E + sqrt(E^2 – 4 * D * F) ) / (2 * D) ,          (x = -E – sqrt(E^2 – 4 * D * F) ) / (2 * D) .
  3. আর area বের করার সমীকরণ , 0.5 * x1 * (y2 – y3)  + x2 * (y3 – y1) + x3 8 (y1 – y2)
  4.  A = 0 না লিখে আমরা ব্যবহার করব fabs(A) <= 1e-9

 

Code :

 

তো আজকের মত এখানেই বিদায় । সামনে ঈণ শা আল্লাহ আমরা আরো অনেক সুন্দর সুন্দর প্রবলেম নিয়ে আলোচনা করব ।

কৃতজ্ঞতা স্বীকার  : ওয়াসিফ মোহাম্মদ ভাই ।