সার্কেল ইউনিয়ন

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

(এই ছবিটা ইউভিএ ১২০৫৬ থেকে নেয়া। প্রবলেম এর লিঙ্ক এখানে।)

এখন তোমাকে সিডিগুলার সেন্টার (center) আর রেডিয়াস (radius) বলে দেয়া হল। এরপর যদি বলা হয় সিডিগুলোর কারণে, টেবিল এর কতটুকু এরিয়া দেখা যাচ্ছে না, তখন তুমি সেটা কিভাবে বের করবে?

হুমম, চিন্তার বিষয়! তোমার নিশ্চয়ই মনে হচ্ছে এত গুলো সিডি দেয়ার কী দরকার ছিলো? দুই তিনটা দিলে ঠিকই বের করা যেত! আসলে দুই তিনটার জন্যে জেনারালাইজড সল্যুশন বের করতে পারলে মনে হয় অনেকগুলা সিডির জন্যেও পারা যাবে! চেষ্টা করে দেখা যাক। এখানে কোনো কোড দিব না, শুধু বেসিক আইডিয়াটা বলবো। আর সেটা থাকলেই তোমরা কোড করে নিতে পারবে। আর এই প্রবলেমটাকেই আমরা বলি সার্কেল ইউনিয়ন অথবা এরিয়া অফ ইউনিয়ন অব সার্কেল (Combined area of overlapping circles)।

এই  প্রবলেমের জন্যে প্রথমেই আমাদেরকে কিছু বিন্দু কে বেশী গুরুত্ব দিতে হবে। তিন ধরনের বিন্দুকে আমি বেশী গুরুত্ব দিব।

১) প্রত্যেকটা বৃত্তের leftmost বিন্দু ( center.x - radius)।
২) প্রত্যেকটা বৃত্তের rightmost বিন্দু ( center.x + radius)।
৩) যে কোনো দুইটা বৃত্তের ছেদবিন্দু (intersection points between two circles)।

টুকরা  টুকরা টুকরা

(এখানে  তিনটা বৃত্তের জন্যে দেখানো হল)

আমরা গুরুত্বপূর্ণ বিন্দুগুলো পেয়ে গেছি! এখন আমরা যে কাজটা করবো তার নাম হল টুকরা টুকরা করা! সুন্দর ভাষায় বলতে গেলে স্লাইসিং (slicing)। ছবিটা দেখেই নিশ্চয়ই বুঝতে পারছো যে স্লাইসিং মানে কী? আমরা আমাদের ইন্টারেস্টিং পয়েন্টগুলিতে একটা করে লম্বা সরলরেখা একে বৃত্ত গুলোকে কতগুলো ডিসজয়েন্ট এলাকায় ভাগ করতে চাচ্ছি।

রাঙিয়ে দাও আমার সবটাকে

ভাগাভাগির কাজ তো শেষ। এখন আলাদা জায়গাগুলোকে আলাদা রং দিলে কেমন হয়?

রং দিয়ে দিলাম, সবগুলো জায়গাকে। এখন বেশ পরিচ্ছন্ন মনে হচ্ছে জায়গা গুলোকে, আগের মতো তালগোল পাকানো মনে হচ্ছে না! কী বলো? এখন দেখে কী একটু একটু মনে হচ্ছে যে এরিয়াটা কোনভাবে বের করে ফেলা যাবে? সবথেকে মজার ব্যাপার হল, বৃত্তের সংখ্যা যত বেশীই হোক না কেন, এভাবে তুমি সব সময়ই সুন্দর সুন্দর রঙিন টুকরা করে ফেলতে পারবে, যারা প্রত্যেকেই হবে নিচের ছবিগুলোর যেকোন একটার মত।

শেষের শুরু

এখন আসলে বাকি কাজটুকু সিম্পল জিওমেট্রি।

বামদিকের ছবিটার জন্যে, p1, p2, p3, p4 জানলে আর বৃত্তদুইটার কেন্দ্র আর ব্যাসার্ধ জানলে খুব সহজেই এরিয়াটা বের করে ফেলা যাবে। এরিয়াটা হবে:

সবুজ p1p2p3p4 ট্রাপিজিয়ামের ক্ষেত্রফল + নীল উপরের বৃত্তাংশটুকুর ক্ষেত্রফল + হলুদ নীচের বৃত্তাংশটুকুর ক্ষেত্রফল

মাঝখানের ছবিটার জন্যে বামদিকের ছবিটার ক্ষেত্রে যা করেছিলে সেইটা যতগুলি এনক্লোজিং এরিয়া আছে ততবার বের করতে হবে। কিন্তু আমরা নিশ্চিত যে এই মাঝখানের গোলাপী এরিয়াগুলি কখনই একে অন্যকে ছেদ করবে না, মানে এই এরিয়াগুলো নিজেদের মাঝে ডিসজয়েন্ট! কারণ আমরা টুকরা করার সময় এই ব্যাপারটা নিশ্চিত করেই এগিয়েছি।

একদম শেষের, ডানদিকের ছবিটা বামদিকের ছবিটারই একটা স্পেশাল কেস, যেখানে উপরের আর নিচের চাপদুটি একই বৃত্তের অংশ। এটাও খুব সহজেই বের করে ফেলা সম্ভব।

এভাবে সবগুলো ভাগের জন্যে আলাদা আলাদা করে এরিয়া বের করে ফেলতে পারলেই তুমি গোটা এরিয়াটা বের করে ফেলতে পারবে, কারণ এই এরিয়াগুলো একটা আরেকটা কে কোনো ভাবেই ওভারল্যাপ করবে না ।

তো হয়ে গেলো আমাদের সার্কেল ইউনিয়ন এর কাজ। এখন তুমি সহজেই এরকম ক্ষেত্রে এরিয়াটা বের করে ফেলতে পারবে।

বি দ্র: এরপরের পোস্টে আমি কোড + কম্প্লেক্সিটি এনালাইসিস দেয়ার চেষ্টা করবো, তার আগে তোমরা আইডিয়াটা নিজে বুঝে কোড করার চেষ্টা করো আর আমাকে জানাও কোথাও কোনো সমস্যা থাকলে। ইউভিএ ১২০৫৬ দিয়েই শুরু করো না!

হ্যাপী কোডিং!