#UVa:477-Points in Figures: Rectangles and Circles

要計算點是否在長方形內,只需要看點之x座標有否在長方形左上角之x座標與長方形右下角之x座標之間,以及點之y座標有否在長方形左上角之y座標與長方形右下角之y座標之間就可以了。

要計算點是否在圓形內,只需要看點與圓心的距離是否小於半徑即可。

C++(0.028)

/*******************************************************/
/* UVa 477 Points in Figures: Rectangles and Circles   */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2011/11/28                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<cmath>
#define ERROR 1e-9
using namespace std;

bool floatequal( float x, float y ){
  return (fabs(x-y) < ERROR);
}

struct Point{
  float x;
  float y;
};

struct Rectangle{
  Point leftup;
  Point rightdown;
};

struct Circle{
  Point center;
  float radius;
};

struct Figure{
  char type;
  union{
    Rectangle rec;
    Circle cir;
  };
};

float dis( Point p1, Point p2 ){
  return sqrt(pow( (p1.x-p2.x), (float)2.0 ) + pow( (p1.y-p2.y), (float)2.0 ));
}

int main(){
  char condition;
  Figure fig[15];
  int total = 0;
  while( scanf( "%c", &condition ) != EOF && condition != '*' ){
    fig[total].type = condition;
    if( condition == 'r' ){
      scanf( "%f%f%f%f", &(fig[total].rec.leftup.x), 
        &(fig[total].rec.leftup.y), 
        &(fig[total].rec.rightdown.x), 
        &(fig[total].rec.rightdown.y));
    }
    else if( condition == 'c' ){
      scanf( "%f%f%f", &(fig[total].cir.center.x),
        &(fig[total].cir.center.y),
        &(fig[total].cir.radius));
    }
    total++;
    getchar(); /* Delete the enter key */
  }
  Point test;
  int pointnum = 1;
  bool containp = 0;
  while( scanf( "%f%f", &(test.x), &(test.y) ) != EOF ){
    if( floatequal( test.x, 9999.9 ) && floatequal( test.y, 9999.9 ) )
      break;

    containp = 0;
    for( int i = 0 ; i < total ; i++ ){
      if( fig[i].type == 'r' ){
        if( test.x > fig[i].rec.leftup.x && test.x < fig[i].rec.rightdown.x )
          if( test.y < fig[i].rec.leftup.y && test.y > fig[i].rec.rightdown.y ){
            printf( "Point %d is contained in figure %d\n", pointnum, i+1 );
            containp = 1;
          }
      }
      else if( fig[i].type == 'c' ){
        if( dis( test, fig[i].cir.center ) < fig[i].cir.radius ){
          printf( "Point %d is contained in figure %d\n", pointnum, i+1 );
          containp = 1;
        }
      }
    }

    if( !containp )
      printf( "Point %d is not contained in any figure\n", pointnum );
    pointnum++;
  }
  return 0;
}

#UVa:476-Points in Figures: Rectangles

要計算點是否在長方形內,只需要看點之x座標有否在長方形左上角之x座標與長方形右下角之x座標之間,以及點之y座標有否在長方形左上角之y座標與長方形右下角之y座標之間就可以了。

C++(0.016)

/*******************************************************/
/* UVa 476 Points in Figures: Rectangles               */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2011/11/28                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<cmath>
#define ERROR 1e-9
using namespace std;

bool floatequal( float x, float y ){
  return (fabs(x-y) < ERROR);
}

struct Point{
  float x;
  float y;
};

struct Rectangle{
  Point leftup;
  Point rightdown;
};

int main(){
  char condition;
  Rectangle rec[15];
  int total = 0;
  while( scanf( "%c", &condition ) != EOF && condition != '*' ){
    scanf( "%f%f%f%f", &(rec[total].leftup.x), 
      &(rec[total].leftup.y), 
      &(rec[total].rightdown.x), 
      &(rec[total].rightdown.y));
    total++;
    getchar(); /* Delete the enter key */
  }
  Point test;
  int pointnum = 1;
  bool containp = 0;
  while( scanf( "%f%f", &(test.x), &(test.y) ) != EOF ){
    if( floatequal( test.x, 9999.9 ) && floatequal( test.y, 9999.9 ) )
      break;

    containp = 0;
    for( int i = 0 ; i < total ; i++ ){
      if( test.x > rec[i].leftup.x && test.x < rec[i].rightdown.x )
        if( test.y < rec[i].leftup.y && test.y > rec[i].rightdown.y ){
          printf( "Point %d is contained in figure %d\n", pointnum, i+1 );
          containp = 1;
        }
    }

    if( !containp )
      printf( "Point %d is not contained in any figure\n", pointnum );
    pointnum++;
  }
  return 0;
}

#UVa:458-The Decoder

利用ASCII碼找出Sample Input和Sample Output相差的k值,將輸入的每個字都以此k值做加減即可得解。

C++(0.172)

/*******************************************************/
/* UVa 458 The Decoder                                 */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2011/11/25                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int main(){
  const int K = (int)('*'-'1');
  string s;
  while( getline( cin, s ) ){
    for( int i = 0 ; i < s.length() ; i++ )
      printf( "%c", s[i]+K );
    printf( "\n" );
  }
  return 0;
}

#UVa:272-TEX Quotes

照著題目要求,更換雙引號即可。

C++(0.016)

/*******************************************************/
/* UVa 272 TEX Quotes                                  */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2011/11/24                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int main(){
  string s;
  bool leftorright = 0;
  while( getline( cin, s ) )
  {
    for( int i = 0 ; i < s.length() ; i++ )
      if( s[i] == '"' ){
        if( leftorright )
          printf( "''" );
        else
          printf( "``" );
        leftorright ^= 1;
      }
      else{
        printf( "%c", s[i] );
      }
    printf( "\n" );
  }
  return 0;
}

#UVa:100-The 3n + 1 problem

照著題目所說的去遞迴即可得解。

C++(0.832)

/*******************************************************/
/* UVa 100 The 3n+1 problem                            */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2011/11/23                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int cyclelength( int n );

int main(){
  int i, j, min_i_j, max_i_j;
  int max_length, term_length;
  while( scanf( "%d%d", &i, &j ) != EOF ){
    max_length = 0;
    min_i_j = (i < j)? i : j;
    max_i_j = (i > j)? i : j;
    for( ; min_i_j <= max_i_j ; min_i_j++ ){
      term_length = cyclelength(min_i_j);
      max_length = (term_length > max_length)? term_length : max_length;
    }
    printf( "%d %d %d\n", i, j, max_length );
  }
  return 0;
}

int cyclelength( int n ){
  if( n == 1 )
    return 1;
  else if( n % 2 )
    return 1+cyclelength(3*n+1);
  else
    return 1+cyclelength(n/2);
}

#UVa:11995-I Can Guess the Data Structure!

三種資料結構都做出來實際操作一遍試試看有哪些會符合即可。

P.S. 要小心有可能會有沒東西但卻要pop出來的情況。

C++(0.020)

/*******************************************************/
/* UVa 11995 I Can Guess the Data Structure!           */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2012/07/22                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
using namespace std;

int main(){
  stack<int> st;
  queue<int> qu;
  priority_queue<int> pq;
  int n, cmd, x;
  bool stack, queue, pqueue;

  while( scanf( "%d", &n ) != EOF ){
    stack = true;
    queue = true;
    pqueue = true;
    for( int i = 0 ; i < n ; i++ ){
      scanf( "%d%d", &cmd, &x );
      if( cmd == 1 ){
        st.push(x);
        qu.push(x);
        pq.push(x);
      }
      else if( cmd == 2 ){
        if( stack ){
          if( !st.empty() && st.top() == x ) st.pop();
          else stack = false;
        }
        if( queue ){
          if( !qu.empty() && qu.front() == x ) qu.pop();
          else queue = false;
        }
        if( pqueue ){
          if( !pq.empty() && pq.top() == x ) pq.pop();
          else pqueue = false;
        }
      }
    }
    if( (stack && queue) || (queue && pqueue) || (stack && pqueue ) )
      printf( "not sure\n" );
    else if( stack ) printf( "stack\n" );
    else if( queue ) printf( "queue\n" );
    else if( pqueue ) printf( "priority queue\n" );
    else printf( "impossible\n" );

    while( !st.empty() ) st.pop();
    while( !qu.empty() ) qu.pop();
    while( !pq.empty() ) pq.pop();

  }
  return 0;
}
共 38 頁 1 36 37 38