যারা প্রোগ্রামিং প্রবলেম সমাধান করেন তাদের কাছে খুবই পরিচিত একটি সাইট Uva Online Judge . এই সাইটটির সবচাইতে বড় সুবিধা, এটিতে প্রচুর সুন্দর সুন্দর প্রবলেম দেয়া আছে । আর জ্যামিতিক প্রবলেম এর জন্য ব্যাপকতায় এই সাইটটির কোন জুড়ি নেই , অসংখ্য প্রবলেম সেখানে দেয়া আছে!
আজকে আমরা আমাদের লেখার পর্বটি সাজিয়েছি UVa- 10112 (Mycam Triangles) দিয়ে । আমরা এখন এই সুন্দর Geometric Problem টি কিভাবে সমাধান করব তা নিয়ে কিছু কথা বলব ।
Problem Link : https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1053
প্রবলেমটি তে মূলত বলা হয়েছে , এখানে কিছু পয়েন্ট দেয়া থাকবে [ সর্বনিম্ন ৪ এবং সর্বোচ্চ ১৫ টি ] আর দেয়া হবে তাদের পরিচয় দানকারী কিছু ইংরেজি বর্ণ । আমাদের কাজ হবে এখান থেকে এমন একটি ত্রিভুজ বের করা যার ক্ষেত্রফল সর্বোচ্চ আর সেটির মাঝে প্রদত্ত বিন্দুগুলোর আর কোনটিকে পাওয়া যাবে না । পরে যেই পয়েণ্ট গুলো দিয়ে সেই ত্রিভুজটি পাওয়া যাবে তার পরিচয় কারী ইংরেজি বর্ণগুলোকে অ্যালফাবেটিক অর্ডারে ছোট থেকে বড় তে প্রিণ্ট করা ।
Algorithm :
১. প্রথমেই আমরা একটি স্ট্রাকচার অ্যারে নিব । এখানে প্রদত্ত প্রত্যেক ইনপুটের জন্য অ্যারেতে প্রদত্ত ইংরেজি বর্ণটি আর তার পয়েণ্ট গুলোকে সেভ করে রাখব ।
২. তারপর আমরা সেটাকে অ্যালফাবেটিক অর্ডারে ছোট থেকে বড় তে সর্ট করব । এতে আমাদের রেজাল্ট প্রিন্ট করতে সুবিধা হবে ।
৩. এখন আমরা একটি O(n^3) লুপ চালাব প্রত্যেক কম্বিনিশন এ ত্রিভুজ বের করার জন্য । তারপর সাথে সাথেই আমরা চেক করব যে এই প্রাপ্ত ত্রিভুজটির মধ্যে আমাদের আর কোন বিন্দু আছে কিনা যেটা ইনপুটে দেয়া । যদি আমরা দেখি যে অন্য কোন বিন্দু এর মধ্যে আছে তাহলে এই ত্রিভুজ নেয়া যাবে না । অন্যথায় নেয়া যাবে । এভাবে আমরা সবচাইতে বড় ক্ষেত্রফল এর ত্রিভুজটি নিব । আর এটিই হবে আমাদের কাঙ্ক্ষিত আউটপুট ।
Equations :
area = 0.5 * [ x1 * (y2 – y3) + x2 * (y3 – y1) + x3 * (y1 – y2) ]
2 * area = [ x1 * (y2 – y3) + x2 * (y3 – y1) + x3 * (y1 – y2) ]
আমরা ইন্টিজার দিয়ে কাজ করব । কারণ আমাদের তো আর এরিয়া প্রিন্ট করতে হবে না যে তার জন্য আমাদের ফ্র্যাকশন নিয়ে কাজ করতে হবে ।
আর কোন পয়েণ্ট ভেতরে আছে কিনা তার জন্য আমরা সেগমেন্টেড ভাবে ক্ষেত্রফল বের করব আর তার সমষ্টি যদি আমাদের কম্বিনশন ত্রিভুজ এর সমান হয় তাহলে সেই বিন্দুটি আমাদের কম্বিনশন ত্রিভুজ এর মধ্যে আছে অন্যথায় নেই ।
area = ABD + ACD + BCD
if(area = আমাদের কম্বিনশন এর ত্রিভুজ এর area) তাহলে এই ত্রিভুজ নেয়া যাবে না । অন্যথায় এটা আমাদের একটা সম্ভাব্য উত্তর ।
Code :
আমরা আগে নিজে ট্রাই করব , আর যদি নিতান্ত না পারি তাহলে নিচের কোডটি দেখব ।
#include <bits/stdc++.h>
using namespace std;
struct info {
char a[4];
int x,y;
}arr[20];
int find_area(int x1,int y1, int x2, int y2, int x3, int y3){
int area;
area = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
return area;
}
bool cmp(struct info p, struct info q) {
if(p.a[0] < q.a[0]) return true;
else return false;
}
int main(void){
int n,i,ans1,j,k,l,ans2,ans3,ans4,found,save;
while(scanf("%d",&n) == 1) {
if(n == 0) break;
char b[4],c[4],d[4];
for(i = 0; i < n; i++){
scanf("%s %d %d",&arr[i].a,&arr[i].x,&arr[i].y);
}
sort(arr, arr + n, cmp);
save = 0;
for(i = 0; i <= n - 1; i++){
for(j = i + 1; j <= n - 1; j++) {
for(k = j+1; k <= n - 1; k++) {
ans1 = find_area(arr[i].x,arr[i].y,arr[j].x,arr[j].y,arr[k].x,arr[k].y);
if(ans1 < 0) ans1 = ans1 * (-1);
found = 0;
for(l = 0; l <= n - 1; l++) {
if(arr[l].x == arr[i].x && arr[l].y == arr[i].y) continue;
if(arr[l].x == arr[j].x && arr[l].y == arr[j].y) continue;
if(arr[l].x == arr[k].x && arr[l].y == arr[k].y) continue;
ans2 = find_area(arr[i].x,arr[i].y,arr[l].x,arr[l].y,arr[j].x,arr[j].y);
if(ans2 < 0) ans2 = ans2 * (-1);
int ans4 = find_area(arr[j].x,arr[j].y,arr[l].x,arr[l].y,arr[k].x,arr[k].y);
if(ans4 < 0) ans4 = ans4 * (-1);
int ans3 = find_area(arr[k].x,arr[k].y,arr[l].x,arr[l].y,arr[i].x,arr[i].y);
if(ans3 < 0) ans3 = ans3 * (-1);
ans2 = ans2 + ans3 + ans4;
if(ans1 == ans2) {
found = 1;
break;
}
}
if(found == 0 && ans1 >= save) {
if(ans1 > save) {
save = ans1;
b[0] = arr[i].a[0];
c[0] = arr[j].a[0];
d[0] = arr[k].a[0];
}
}
}
}
}
printf("%c%c%c\n",b[0],c[0],d[0]);
}
return 0;
}
তো আজকের মত এখানেই বিদায় ।
আমরা ঈন শা আল্লাহ সামনে আর ও অনেক সুন্দর সুন্দর প্রবলেম নিয়ে আলোচনা করব । ততদিন সবাই ভাল থাক আর বেশি বেশি প্রবলেম সল্ভ করতে থাক ।