IT/소스코드

[C++] Orchard Trees

zzun 2004. 6. 4. 05:11
반응형
http://acm.uva.es/p/v1/143.html

/**
Orchard Trees
zzun
hello82@unitel.co.kr
http://zzun.net
**/

#include <iostream.h>
#include <fstream.h>

ifstream fin;

void swap(float& a, float& b)
{
       float temp = a; a = b; b = temp;
}

bool read_input(float* x, float* y)
{
       bool rtn = false;
       for (int i=0; i<3; i++)
       {
               fin >> x[i] >> y[i];
               if ( x[i] > 0 || y[i] > 0 )
                       rtn = true;
       }

       return rtn;
}

int main()
{
       fin.open("test.in");
       float* x = new float[3];
       float* y = new float[3];
       int cur_y, count, tx1, tx2;
       float a1, a2, cur_x1, cur_x2;
       bool turn;

       while ( read_input(x, y) )
       {
               if ( y[1] < y[0] && y[1] <= y[2] )
               {
                       swap( x[0], x[1] );
                       swap( y[0], y[1] );
               }
               else if ( y[2] < y[0] && y[2] < y[1] )
               {
                       swap( x[0], x[2] );
                       swap( y[0], y[2] );
               }        // for largest y

               count = 0;
               turn = false;
               cur_y = (int) y[0];

               a1 = (x[1]-x[0])/(y[1]-y[0]);
               a2 = (x[2]-x[0])/(y[2]-y[0]);

               if ( a1 > a2 ) // which is on left side
               {
                       swap( x[1], x[2] );
                       swap( y[1], y[2] );
                       swap( a1, a2 );
               }

               cur_x1 = x[0] + a1*((float)cur_y - y[0]);
               cur_x2 = x[0] + a2*((float)cur_y - y[0]);

               while ( 1 )
               {                        
                       cur_y++;

                       if ( !turn && cur_y > y[1] && cur_y <= y[2] ) // find turning point
                       {
                               a1 = (x[2]-x[1])/(y[2]-y[1]);
                               cur_x1 = x[1] + a1*((float)cur_y - y[1]);
                               cur_x2 += a2;
                               turn = true;
                       }
                       else if ( !turn && cur_y > y[2] && cur_y <= y[1] )
                       {
                               a2 = (x[1]-x[2])/(y[1]-y[2]);
                               cur_x2 = x[2] + a2*((float)cur_y - y[2]);
                               cur_x1 += a1;
                               turn = true;
                       }
                       else
                       {
                               cur_x1 += a1;
                               cur_x2 += a2;
                       }

                       if ( (cur_y<=y[1] || cur_y<=y[2]) && cur_y<100 )
                       {
                               tx1 = ( cur_x1-(int)cur_x1 == 0 ) ? (int)cur_x1 : (int)cur_x1+1;
                               tx1 = ( tx1 == 0 ) ? 1 : tx1;
                               tx2 = ( (int)cur_x2 == 100 ) ? 99 : (int)cur_x2; // no point at 0&100
                               count += tx2 - tx1 + 1;
                       }
                       else
                               break;
               }
               
               cout << count << endl;
       }

       fin.close();
}
반응형