[GUIDE] UVa OJ - 375 - Inscribed Circles and Isosceles Triangles
শুরুতেই এই প্রব্লেমটা সহজ ভাষায় ব্যাখ্যা করার চেষ্টা করি ।
Figure : 1 খেয়াল করো । একটি সমদ্বিবাহু ত্রিভুজের ভূমি b এবং উচ্চতা h দেওয়া আছে । প্রথমে এর তিনটি কোণকে সমদ্বিখণ্ডিত করতে হবে । সমত্রিখণ্ডক তিনটির ছেদবিন্দু (চিত্রে O বিন্দু)-কে কেন্দ্র করে এমন একটি বৃত্ত আঁকতে হবে যেটি ত্রিভুজের ৩টি বাহুকে স্পর্শ করে । তারপর আরও একটি বৃত্ত (এই রঙের) আঁকতে হবে যেটি ত্রিভুজের সমান দুই বাহু (চিত্রে AB এবং AC) কে এবং তার নিচের বৃত্তকেও (এই রঙের) স্পর্শ করে । এর উপরের বৃত্তগুলোও এভাবে এঁকে যেতে হবে । কিন্তু এভাবে তো অসীম সংখ্যক বার যাওয়া যাবে; তাহলে থামবো কোথায় ?
এই প্রশ্নের উত্তর মূল স্টেটমেন্টেই দেওয়া আছে । এই যে বৃত্তের একটা Stack তৈরি হচ্ছে, যে বৃত্তের ব্যাসার্ধ 0.000001 এর চেয়ে ছোট হয়ে যাবে, তখনই আমাদের থেমে যেতে হবে !
প্রব্লেমের আউটপুটে দিতে হবে Stack এর সবগুলো বৃত্তের পরিধির যোগফল । তো, বৃত্তের পরিধি হিসেব করতে হলে আমাদের কী জানতে হবে ? অবশ্যই বৃত্তের ব্যাসার্ধ । কীভাবে আমরা এই বৃত্তগুলোর ব্যাসার্ধ বের করতে পারি ?
প্রথমে আমরা Figure : 1 এর ΔABC থেকে ΔABD কে আলাদা করে নিই । Figure : 2 খেয়াল করো । যেহেতু ΔABC একটি সমদ্বিবাহু ত্রিভুজ, সেহেতু BAD কোণের সমদ্বিখণ্ডক রেখা AD বাহু ত্রিভুজের ভুমি BC কে D বিন্দুতে সমদ্বিখণ্ডিত করবে । Figure : 2 থেকে আমরা θ এর মান পেলাম ।
এবার আমরা ΔABC থেকে ΔODC কে আলাদা করে নিই । Figure : 3 খেয়াল করো । শর্তমতে, OCD কোণ θ/2 এর সমান এবং OD বাহু বৃত্তের (এই রঙের) ব্যাসার্ধ । এই তথ্য থেকে আমরা বৃত্তের ব্যাসার্ধ r বের করে ফেললাম ।
এখন, 2 * PI * r এই সূত্র দিয়ে বৃত্তের পরিধি বের করতে পারি !
এবার আসি, পরবর্তি ধাপে । দ্বিতীয় বৃত্তের (এই রঙের) ব্যাসার্ধ বের করার আগে আরেক বার Figure : 1 খেয়াল করো । EF রেখাটি ΔABC কে ভাগ করে ΔAEF তৈরি করছে, যেটিও একটি সমদ্বিবাহু ত্রিভুজ ! প্রথম বৃত্তটি (এই রঙের) ঠিক যেভাবে ΔABC কে স্পর্শ করেছিলো, দ্বিতীয় বৃত্তটিও (এই রঙের) ঠিক একইভাবে ΔAEF কে স্পর্শ করেছে । তাহলে এই বৃত্তের ব্যাসার্ধের হিসেবও আগের মতোই করতে হবে । কিন্তু এই বৃত্তে b এবং h এর মান তো পরিবর্তিত হয়ে গিয়েছে । তাহলে নতুন বৃত্তের ব্যাসার্ধ বের করার আগে পরিবর্তিত b এবং h এর মান বের করে নিতে হবে ।
পরিবর্তিত h এর নাম দিলাম h' । Figure : 4 খেয়াল করো কীভাবে h' এর মান বের করেছি । একদম প্রথম বৃত্তটিকে বের করে নিলাম AD বাহু সহ । তাহলে, বৃত্তের ব্যাসার্ধ যদি OD = r হয়, তবে এই বৃত্তের ব্যাস অবশ্যই GD = 2r হবে । সম্পূর্ণ AD থেকে GD বাদ দিলেই তো আমরা h' পেয়ে যাচ্ছি ।
এবার আমাদের সর্বশেষ কাজ হলো পরিবর্তিত b তথা b' এর মান বের করা ।
Figure : 5 খেয়াল করো । Figure : 1 থেকে ΔABD এবং ΔAEG কে আলাদা করে নিলাম । ত্রিভুজ দুটি একই না হলেও এরা কিন্তু সদৃশ ত্রিভুজ । সদৃশ ত্রিভুজের সদৃশ বাহুগুলোর অনুপাত পরস্পর সমান হয় । তার অর্থ হলো, EG : BD = AG : AD । এখান থেকে আমরা b' এর মানও পেয়ে যাই ।
তাহলে আমরা এই b' এবং h' এর মান Figure : 3 এ ব্যবহৃত সূত্রে বসিয়ে দ্বিতীয় বৃত্তটির (এই রঙের) ব্যাসার্ধ বের করতে পারবো ।
এরপর আবার এই বৃত্তের পরিধি বের করে আগের পরিধির সাথে যোগ করতে হবে । বৃত্তের ব্যাসার্ধ বের করার প্রক্রিয়া আমাদেরকে ততোক্ষণ পর্যন্ত চালিয়ে যেতে হবে যতোক্ষণ না পর্যন্ত 0.000001 এর চেয়ে ছোট ব্যাসার্ধের বৃত্ত আমরা পাচ্ছি ।
এখানে আমার সলুশানের সোর্স কোড দিলাম ।
Figure : 1 খেয়াল করো । একটি সমদ্বিবাহু ত্রিভুজের ভূমি b এবং উচ্চতা h দেওয়া আছে । প্রথমে এর তিনটি কোণকে সমদ্বিখণ্ডিত করতে হবে । সমত্রিখণ্ডক তিনটির ছেদবিন্দু (চিত্রে O বিন্দু)-কে কেন্দ্র করে এমন একটি বৃত্ত আঁকতে হবে যেটি ত্রিভুজের ৩টি বাহুকে স্পর্শ করে । তারপর আরও একটি বৃত্ত (এই রঙের) আঁকতে হবে যেটি ত্রিভুজের সমান দুই বাহু (চিত্রে AB এবং AC) কে এবং তার নিচের বৃত্তকেও (এই রঙের) স্পর্শ করে । এর উপরের বৃত্তগুলোও এভাবে এঁকে যেতে হবে । কিন্তু এভাবে তো অসীম সংখ্যক বার যাওয়া যাবে; তাহলে থামবো কোথায় ?
এই প্রশ্নের উত্তর মূল স্টেটমেন্টেই দেওয়া আছে । এই যে বৃত্তের একটা Stack তৈরি হচ্ছে, যে বৃত্তের ব্যাসার্ধ 0.000001 এর চেয়ে ছোট হয়ে যাবে, তখনই আমাদের থেমে যেতে হবে !
প্রব্লেমের আউটপুটে দিতে হবে Stack এর সবগুলো বৃত্তের পরিধির যোগফল । তো, বৃত্তের পরিধি হিসেব করতে হলে আমাদের কী জানতে হবে ? অবশ্যই বৃত্তের ব্যাসার্ধ । কীভাবে আমরা এই বৃত্তগুলোর ব্যাসার্ধ বের করতে পারি ?
প্রথমে আমরা Figure : 1 এর ΔABC থেকে ΔABD কে আলাদা করে নিই । Figure : 2 খেয়াল করো । যেহেতু ΔABC একটি সমদ্বিবাহু ত্রিভুজ, সেহেতু BAD কোণের সমদ্বিখণ্ডক রেখা AD বাহু ত্রিভুজের ভুমি BC কে D বিন্দুতে সমদ্বিখণ্ডিত করবে । Figure : 2 থেকে আমরা θ এর মান পেলাম ।
এবার আমরা ΔABC থেকে ΔODC কে আলাদা করে নিই । Figure : 3 খেয়াল করো । শর্তমতে, OCD কোণ θ/2 এর সমান এবং OD বাহু বৃত্তের (এই রঙের) ব্যাসার্ধ । এই তথ্য থেকে আমরা বৃত্তের ব্যাসার্ধ r বের করে ফেললাম ।
এখন, 2 * PI * r এই সূত্র দিয়ে বৃত্তের পরিধি বের করতে পারি !
এবার আসি, পরবর্তি ধাপে । দ্বিতীয় বৃত্তের (এই রঙের) ব্যাসার্ধ বের করার আগে আরেক বার Figure : 1 খেয়াল করো । EF রেখাটি ΔABC কে ভাগ করে ΔAEF তৈরি করছে, যেটিও একটি সমদ্বিবাহু ত্রিভুজ ! প্রথম বৃত্তটি (এই রঙের) ঠিক যেভাবে ΔABC কে স্পর্শ করেছিলো, দ্বিতীয় বৃত্তটিও (এই রঙের) ঠিক একইভাবে ΔAEF কে স্পর্শ করেছে । তাহলে এই বৃত্তের ব্যাসার্ধের হিসেবও আগের মতোই করতে হবে । কিন্তু এই বৃত্তে b এবং h এর মান তো পরিবর্তিত হয়ে গিয়েছে । তাহলে নতুন বৃত্তের ব্যাসার্ধ বের করার আগে পরিবর্তিত b এবং h এর মান বের করে নিতে হবে ।
পরিবর্তিত h এর নাম দিলাম h' । Figure : 4 খেয়াল করো কীভাবে h' এর মান বের করেছি । একদম প্রথম বৃত্তটিকে বের করে নিলাম AD বাহু সহ । তাহলে, বৃত্তের ব্যাসার্ধ যদি OD = r হয়, তবে এই বৃত্তের ব্যাস অবশ্যই GD = 2r হবে । সম্পূর্ণ AD থেকে GD বাদ দিলেই তো আমরা h' পেয়ে যাচ্ছি ।
এবার আমাদের সর্বশেষ কাজ হলো পরিবর্তিত b তথা b' এর মান বের করা ।
Figure : 5 খেয়াল করো । Figure : 1 থেকে ΔABD এবং ΔAEG কে আলাদা করে নিলাম । ত্রিভুজ দুটি একই না হলেও এরা কিন্তু সদৃশ ত্রিভুজ । সদৃশ ত্রিভুজের সদৃশ বাহুগুলোর অনুপাত পরস্পর সমান হয় । তার অর্থ হলো, EG : BD = AG : AD । এখান থেকে আমরা b' এর মানও পেয়ে যাই ।
তাহলে আমরা এই b' এবং h' এর মান Figure : 3 এ ব্যবহৃত সূত্রে বসিয়ে দ্বিতীয় বৃত্তটির (এই রঙের) ব্যাসার্ধ বের করতে পারবো ।
এরপর আবার এই বৃত্তের পরিধি বের করে আগের পরিধির সাথে যোগ করতে হবে । বৃত্তের ব্যাসার্ধ বের করার প্রক্রিয়া আমাদেরকে ততোক্ষণ পর্যন্ত চালিয়ে যেতে হবে যতোক্ষণ না পর্যন্ত 0.000001 এর চেয়ে ছোট ব্যাসার্ধের বৃত্ত আমরা পাচ্ছি ।
এখানে আমার সলুশানের সোর্স কোড দিলাম ।
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
const double EPS = 1e-6; | |
//const double PI = 4 * atan(1.0); /// RUN TIME : 0.090 | |
const double PI = acos(-1.0); /// RUN TIME : 0.070 | |
//const double PI = 3.14159265358979323846; /// RUN TIME : 0.070 | |
int main() | |
{ | |
//freopen("in.txt","r",stdin); | |
//freopen("out.txt","w", stdout); | |
int test; | |
double b, h, b_prime, h_prime, r, sum; | |
scanf("%d", &test); | |
while (test--) { | |
scanf("%lf%lf", &b, &h); | |
sum = 0; | |
while (1) { | |
r = tan(atan((2 * h) / b) / 2) * (b / 2); | |
if (r < EPS) { | |
break; | |
} | |
sum += 2 * PI * r; | |
h_prime = h - 2 * r; | |
b_prime = (b * h_prime) / h; | |
h = h_prime; | |
b = b_prime; | |
} | |
printf("%13.6lf\n", sum); | |
/// Printing a blank line between consecutive test cases except the last test case | |
if (test) { | |
printf("\n"); | |
} | |
} | |
return 0; | |
} |
Comments
Post a Comment