আজকে আমরা আরেকটি প্রোগ্রামিং প্রবলেম নিয়ে আলোচনা করব । আমরা ইতোমধ্যে বিভিন্ন অনলাইন জাজ এর কিছু প্রবলেম নিয়ে আলোচনা করেছি । কম্পিউটার বিজ্ঞান এর একটি অত্যন্ত গুরুত্বপূর্ণ শাখা হচ্ছে প্রোগ্রামিং প্রবলেম সমাধান । এতে আমাদের চিন্তার দক্ষতা যেমন বাড়ে , ঠিক তেমনিভাবে আমাদের একাডেমিক এবং জ্ঞানের পরিধি ও বাড়াতে এটি খুবই সহায়ক ।
তো প্রবলেম পাওয়ার জন্য অসংখ্য সাইট বা অনলাইন জাজ রয়েছে । এর মধ্যে খুবই পরিচিত একটি সাইট 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 এর স্থানাংক বের করব ।
আমরা ব্যাপারটিকে একটু ছবিতে দেখাই
Equations :
- লাইন সমীকরণ : Ax + BY = C
- 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) .
- আর area বের করার সমীকরণ , 0.5 * x1 * (y2 – y3) + x2 * (y3 – y1) + x3 8 (y1 – y2)
- A = 0 না লিখে আমরা ব্যবহার করব fabs(A) <= 1e-9
Code :
#include <bits/stdc++.h> #define EPS 1e-9 using namespace std; double distance(double x1, double y1, double x2,double y2) { double value; value = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); value = sqrt(value); return value; } double find_point(double x1,double m,double x2, double n){ double value; value = m * x2 + n * x1; value = value / (m + n); return value; } double tri_area(double x1,double y1,double x2,double y2,double x3,double y3) { double value; value = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2); return value; } void line_intersection(double xa,double ya, double d,double xp,double yp,double b,double arrx[5],double arry[5]) { double A,B,C; A = 2 * (xp - xa); B = 2 * (yp - ya); C = xa * xa - xp * xp + ya * ya - yp * yp + b * b - d * d; double D,E,F,value; double ansx1,ansx2,ansy1,ansy2; if(fabs(A) <= EPS && B != 0) { ansy1 = (- C * 1.0 / B); ansy2 = ansy1; value = d * d - (ansy1 - ya) * (ansy1 - ya); value = sqrt(value); ansx1 = xa + value; ansx2 = xa - value; } else if(fabs(B) <= EPS && A != 0) { ansx1 = (- C * 1.0) / A; ansx2 = ansx1; value = d * d - (ansx1 - xa) * (ansx1 - xa); value = sqrt(value); ansy1 = ya + value; ansy2 = ya - value; } else { D = A * A + B * B; E = 2 * B * C + 2 * A * B * xa - 2 * A * A * ya; F = C * C + A * A * xa * xa + 2 * C * A * xa + A * A * ya * ya - A * A * d * d; value = E * E - 4.0 * D * F; value = sqrt(value); ansy1 = (- E + value) / (2.0 * D); ansy2 = (- E - value) / (2.0 * D); ansx1 = -(B * ansy1 + C) / A; ansx2 = -(B * ansy2 + C) / A; } double area1,area2; area1 = tri_area(xa,ya,xp,yp,ansx1,ansy1); area2 = tri_area(xa,ya,xp,yp,ansx2,ansy2); if(area1 > 0) { arrx[0] = ansx1; arry[0] = ansy1; } if(area2 > 0) { arrx[0] = ansx2; arry[0] = ansy2; } } int main(void) { int T,t; double xa,ya,xb,yb,xc,yc,xp,yp,xq,yq; double a,b,c,d; double area; scanf("%d",&T); for(t = 1; t <= T;t++) { scanf("%lf %lf %lf %lf %lf %lf %lf",&xa,&ya,&xb,&yb,&b,&c,&d); double darrx[5],darry[5],carrx[5],carry[5]; a = distance(xa,ya,xb,yb); xp = find_point(xa,a-c,xb,c); yp = find_point(ya,a-c,yb,c); line_intersection(xa,ya,d,xp,yp,b,darrx,darry); double xd = darrx[0]; double yd = darry[0]; xq = find_point(xa,c,xb,a-c); yq = find_point(ya,c,yb,a-c); line_intersection(xq,yq,d,xb,yb,b,carrx,carry); double xc = carrx[0]; double yc = carry[0]; printf("Case %d:\n",t); printf("%0.8lf %0.8lf %0.8lf %0.8lf\n",xc,yc,xd,yd); } return 0; }
তো আজকের মত এখানেই বিদায় । সামনে ঈণ শা আল্লাহ আমরা আরো অনেক সুন্দর সুন্দর প্রবলেম নিয়ে আলোচনা করব ।
কৃতজ্ঞতা স্বীকার : ওয়াসিফ মোহাম্মদ ভাই ।