CodeForces 239A. Triangle

Link: 　　http://codeforces.com/contest/407/problem/A

给定直角三角形的2个直角边a，b。求在直角坐标系中，是否存在对应的直角三角形，使得三个定点都在整点上，并且三边都不和坐标轴平行。

如果存在，输出YES，和三个点的坐标。否则输出NO

很显然，为了方便，可以把原点作为一个顶点。

这道题目做的时候少考虑了很多情况。

比如：

如何使得边不和坐标轴平行？要保证要求的另外两个点的横坐标或者纵坐标不能相等。

如何保证三角形是直角三角形？只需要保证，另外两个点和坐标轴围成的三角形相似。

因为范围是1000,所以可以暴力求解。复杂度O（10^6）

 /*
  * =====================================================================================
  *       Filename : triangle.cpp
  *    Description : triangle
  *    Version     : 0.1
  *        Created : 03/30/14 15:57
  *         Author : Liu Xue Yang (LXY), liuxueyang457@163.com
  *         Motto  : How about today?
  * =====================================================================================
  */
 #include <cmath>
 #include <cstdio>
 #include <cstdlib>
 #include <iostream>
 using namespace std;

 /*
  * ===  FUNCTION  ======================================================================
  *         Name:  gcd
  *  Description:  gcd
  * =====================================================================================
  */
     int
 gcd ( int a, int b )
 {
      ? a : gcd(b, a % b);
 }        /* -----  end of function gcd  ----- */
 /*
  * ===  FUNCTION  ======================================================================
  *         Name:  test
  *  Description:  test
  * =====================================================================================
  */
     void
 test ( int xa, int ya, int xb, int yb )
 {
     if ( xa == xb || ya == yb ) {
         return;
     }
     printf ( "YES\n" );
     printf ( "0 0\n" );
     printf ( "%d %d\n", xa, ya );
     printf ( "%d %d\n", xb, yb );
     exit();
     return ;
 }        /* -----  end of function test  ----- */

 /*
  * ===  FUNCTION  ======================================================================
  *         Name: main
  * =====================================================================================
  */

     int
 main ( int argc, char *argv[] )
 {
     int a, b;
     scanf ( "%d%d", &a, &b );
     ; x < a; ++x ) {
         ; y < a; ++y ) {
             if ( x * x + y * y == a * a ) {
                 int g = gcd(x, y);
                 int dx = x / g, dy = y / g, u = dx * dx + dy * dy;
                 int v = b * b, ratio = v / u, k = (int)sqrt(ratio) ;
                 if ( v % u ) {
                     continue;
                 }
                 if ( k * k != ratio ) {
                     continue;
                 }
                 test(x, y, dy * k, -dx * k);
                 test(x, y, -dy * k, dx * k);
             }
         }
     }
     puts("NO");

         return EXIT_SUCCESS;
 }                /* ----------  end of function main  ---------- */

这是tourist的代码

巴特西

CodeForces 239A. Triangle

最新文章

热门文章