আলোচনাঃ
আমাকে কতগুলো cube এর স্থানাংক(দুইটা corner এর স্থানাংক) দেয়া থাকবে। আমাকে বলতে হবে যে, cube গুলোর intersection এর volume কত হবে। মানে কি? উপরের চিত্র তে 2 no case টার 2D ছবি দেয়া হয়েছে(ধরে নিই এগুলো cube). সবুজ রং এর cube টার নিচের corner এর স্থানাংক (x1,y1,z1) এবং উপরের corner এর স্থানাংক (x2,y2,z2). এই cube এর ভেতরে আছে কমলা রং এর cube. আবার এর ভেতরে আছে বেগুনি রং এর cube. তাহলে এই তিন cube এর intersection volumn কি বেগুনি রং এর cube টার volume হওয়ার কথা না? কারণ তিনটা cube এরই common area হচ্ছে বেগুনি রং cube টার volume.
উত্তরঃ
আমরা জানি, আয়তন = দৈর্ঘ্য * প্রস্থ * উচ্চতা
তাহলে এদের মান জানলেই হবে। কিন্তু বেগুনি রং এর cube এর দৈর্ঘ্য ,প্রস্থ ও উচ্চতাই বা কতো?
চিত্র থেকে দেখতে পাচ্ছি, বেগুনি রং এর cube এর left lower corner এর x1,y1,z1 হচ্ছে, সবগুলো cube এর x1,y1,z1 এর মধ্যে সব থেকে বড় মান। অপরদিকে, বেগুনি রং এর cube এর right upper corner এর x2,y2,z2 হচ্ছে, সবগুলো cube এর x2,y2,z2 এর মধ্যে সব থেকে ছোট মান। তাহলে আমাদের বের করা দরকার সব x1,y1,z1 এর মধ্যকার বড় মান এবং সব x2,y2,z2 এর মধ্যকার ছোট মান।
আর দৈর্ঘ্য ,প্রস্থ ও উচ্চতার মান হবে বড় মান থেকে ছোট মান এর বিয়োগফল।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
#define PI acos(-1.0)
int main(){
int t,x1,x2,y1,y2,z1,z2;
cin>>t;
for(int i=1;i<=t;i++){
int n;
cin>>n;
int xLow=0,yLow=0,zLow=0;
int xHigh=1005,yHigh=1005,zHigh=1005;
for(int j=0;j<n;j++){
cin>>x1>>y1>>z1>>x2>>y2>>z2;
xLow=max(xLow,x1);
xHigh=min(xHigh,x2);
yLow=max(yLow,y1);
yHigh=min(yHigh,y2);
zLow=max(zLow,z1);
zHigh=min(zHigh,z2);
}
int ans=(xHigh-xLow)*(yHigh-yLow)*(zHigh-zLow);
printf("Case %d: %d\n",i, ans>0 ? ans: 0);
// if ans = 0 ,then there is no common volume
}
}