1305 - Area of a Parallelogram

সমস্যাটি খুব-ই সোজা মানের । এটি সমাধানের জন্য যে knowledge থাকা লাগবে টা একজন উচ্চমাধ্যমিক শিক্ষার্থীর রয়েছে ।  আমরা প্রথমে সমস্যাটি সমাধানের জন্য প্রয়োজনীয় concept এর আলোচনা করব এবং পরে সমস্যাটি সমাধানের জন্য প্রয়োজনীয় step অবলম্বন করব ।

Problem Specification :
          তোমাকে একটি সামান্তরিক দেয়া হল যার প্রথম তিনটি স্থানাঙ্ক তুমি জান । মনে কর, সেই গুলিহল , Ax,Ay,Bx,By,Cx,Cy . চতুর্থ বাহুর স্থানাঙ্ক হল Dx,Dy .
                                        
          এখন তোমাকে চতুর্থ বাহুর স্থানাঙ্ক এবং সামান্তরিকটির ক্ষেত্রফল বের করা লাগবে ।

Theory of Solution :

          সামান্তরিকের তিনটি বাহুর স্থানাঙ্ক জানা থাকলে চতুর্থ বাহুর স্থানাঙ্ক খুব সহজেই নিচের ফর্মুলা অনুসারে বের করা যায় ।

          Dx = Ax + Cx-Bx
          Dy = Ay+Cy - By

         Area নির্ণয় করার কোন সুত্র উচ্চমাধ্যমিক পর্যায়ে পরে এসেছ ? ঠিকই ধরতে পেরেছ । Area নির্ণয় এর ফর্মুলা হবেঃ
                 

          q=((Ax*By)+(Bx*Cy)+(Cx*Dy)+(Dx*Ay))-((Ay*Bx)+(By*Cx)+(Cy*Dx)+(Dy*Ax));
          area=0.5*q;

সতর্কতাঃ
      Co-ordinate এর অবস্থানের কারণে Area এর মান negative আসতে পারে । কাজেই Check করে নাও ।
Program Outline:

#include<stdio.h>
int main()
{
    int a,ax,ay,bx,by,cx,cy,dx,dy,area,i,q;
    scanf("%d",&a);
    for(i=0;i<a;i++){
        scanf("%d%d%d%d%d%d",&ax,&ay,&bx,&by,&cx,&cy);
        dx=cx+ax-bx;
        dy=cy+ay-by;
        q=((ax*by)+(bx*cy)+(cx*dy)+(dx*ay))-((ay*bx)+(by*cx)+(cy*dx)+(dy*ax));
        if(q<0)
            q*=-1;
        area=0.5*q;
        printf("Case %d: %d %d %d\n",i+1,dx,dy,area);
    }
}

     

  

Solution Of Lifht Online Judge 1294 - Positive Negative Sign

            সমস্যাটি আসলেই খুব-ই সোজা । একবার ধরে ফেলতে পারলে মনে হবে এইরকম সমস্যাও ACM এ দেয় ? তাহলে চল দেখা যাক আসলেই কি জানতে চাওয়া হচ্ছে এই সমস্যায় ?

         চল আমরা প্রথম Input/output এর দিকে নজর দেই । যখন n=12 এবং m = 3 তখন সমস্যাটি অনেকটা হয়ে যায় এই রকমঃ
                    -1 -2 -3 +4 +5 +6 -7 -8 -9 +10 +11 +12 
     
       যার উত্তর হলঃ ১৮ ।  n এর মান ছোট তখন আমরা সহজেই এর মান বের করে ফেলতে পারি । কিন্তু n এর মান বড় হলে ?

    সময় এখন উপরের সমস্যাটিকে ভেঙ্গে দেখার ।

           -1 +4 = 3               -7 + 10 =3
           -2+ 5 = 3               -8 + 11 =3
            -3 + 6 =3              -9 + 12 =3

দেখতেই পাচ্ছ যোগ-বিয়োগের ফলে n সংখ্যক terms হয়ে গেছে n/2 সংখ্যক terms যাদের প্রত্যেকের মান হল m সুতরাং   যোগফল  =  m + m + m + .............................( n/2 সংখ্যক terms )
                               =  m * ( 1 + 1+ 1 + .................    ( n/2 সংখ্যক terms )   )
                               = m* ( n/2 )

কাজেই সমাধান হলঃ  result = m* ( n/2 ) .

             শেষে শুধুই একটি warning : result variable এর type long long রাখতে ভুল না  । শুভ কামনার সবটুকু তোমার জন্য রেখে আজকে না হয় এখানেই বিদায় নিলাম । ভাল থেক সবসময় ।   

Solution of Light Online Judge 1249 - Chocolate Thief

        Problem টির Category হল Beginers Level . So যারা programming এর জগতে উঁকি দিতে আরম্ভ করেছ তাদের জন্য এই সমস্যাটি অনায়াসে Solve করে ফেলার মত । চল দেখা যাক আসলে এই সমস্যাটিতে কি জানতে চাওয়া হচ্ছে ।
        প্রথমে আমরা নজর দিব Sample Input/Output এর দিকে । আমি যদি সবার চকলেট এর আয়তন বের করি তাহলে অনেকটা নিচের মত দেখাবে ।
      
                                                 চকলেটের আয়তন

     atq 3 4 3  -----   ৩৬       

     mun 10 4 1 -----   ৪০

     sam1 6 6 1 -----   ৩৬

     sam2 18 2 1 -----  ৩৬

     mub 1 36 1 ------  ৩৬

     tan 1 4 9  ------  ৩৬

     sha 4 3 3  ------  ৩৬

     di 3 12 1  ------  ৩৬

     nab 2 2 9  ------  ৩৬

     all 8 4 1  ------  ৩৬

     fah 3 2 6  ------  ৩৬

তাহলে  চকলেট এর আয়তন অনুযায়ী যদি আমি সবাইকে Sort করে ফেলি তবে তা অনেকটা নিচের মত দেখাবে ।

                                              চকলেটের আয়তন

     all 8 4 1  ------  ৩২

     atq 3 4 3  -----   ৩৬       

     sam1 6 6 1 -----   ৩৬

     sam2 18 2 1 -----  ৩৬

     mub 1 36 1 ------  ৩৬

     tan 1 4 9  ------  ৩৬

     sha 4 3 3  ------  ৩৬

     di 3 12 1  ------  ৩৬

     nab 2 2 9  ------  ৩৬

     fah 3 2 6  ------  ৩৬
     mun 10 4 1 -----   ৪০

      এ হতে দেখা যাচ্ছে যে সর্বনিন্ম মান হল ৩২ এবং সর্বোচ্চ মান হল ৪০ । যেহেতু মান দুইতি সমান নয় কাজেই mun চকলেট চুরি করেছে  all হতে ।

     এখনও যারা বুজতে পারনি সমস্যাটি কিভাবে সমাধান করবে জন্যই বলছি সমস্যাটিতে আসলে জানতে চাওয়া হচ্ছে একটি array এর সর্বোচ্চ ও সর্বনিন্ম মান বের করতে হবে । যদি তারা সমান হয় তাহলে চুরি হয়নি । আর তা না হলে চুরি হয়েছে । Simple , তাই না ?

Code:

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

class People
{
public:
    int a;
    string nme;
    People(string a ,int n):nme(a),a(n){}
    People();
};

bool cmp(People A,People B)
{
    return A.a < B.a ;
}


int main()
{
    int j,n,t1,t2,t3,i,test;
    string a;
    vector<People> pp;
    cin>>test;
    for(i=1;i<=test;i++)
    {
        cin>>n;
        for(j=0;j<n;j++)
        {
            cin>>a>>t1>>t2>>t3;
            pp.push_back( People(a,t1*t2*t3) ) ;
        }
        sort(pp.begin(),pp.end(),cmp);
        if( pp[0].a == pp[pp.size()-1].a )
            cout<<"Case "<<i<<": no thief"<<endl;
        else
            cout<<"Case "<<i<<": "<<pp[0].nme<<" took chocolate from "<<pp[pp.size()-1].nme<<endl;
    }

    return 0;
}