2014-03-29

Codeforces #239 Div.2 C Triangle

本题惨状不可言表。

做完之后只见房间里Hack无数。Div.1那边更加激烈，某些人甚至Hack成功20次+

我的错误代码神奇的挺过了一次Hack。。。最终跪在了System Test上。

然后发现我的代码有两个问题。。。。。。。。。。

先来说下题目：

这道题的意思就是给你两个数，代表一个直角三角形的两条直角边。然后让你找到这个三角形，但是必须符合以下要求：

1. 三角形的三个点都在整点上。

2. 三角形的三条边都不能坐标轴平行。（←，我第一次就没有注意这一点，只判断了两条直角边不能与坐标轴平行）

我的解法是枚举两个点可能的坐标。要求产生a^2+b^2=c^2这样的一组数a, b，其中c是输入的其中一个数。

找到这个之后就可以构造三角形了。

另两个坑点是，需要判断第三条边是否平行于坐标轴，就是两个Y值不能相同。

另一个坑点是，有些数字产生的形如a^2+b^2=c^2的a和b不只有一组，所以需要都把它们弄下来。

最后我还是勉勉强强的通过了这题。。下面是AC代码（C#）：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Text.RegularExpressions; 
using System.Threading.Tasks; 

namespace test05 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            new Solve().run(); 

            //Pause 
            //Remeber Comment it!!! 
            //Console.Write("==================nPause..."); Console.Read(); 
        } 
    } 
    class Solve 
    { 
        public void run() 
        { 
            string[] tempInput = Console.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); 
            int a = int.Parse(tempInput[0]); 
            int b = int.Parse(tempInput[1]); 

            List<int[]> ka = isright(a); 
            if (ka.Count == 0) 
            { 
                Console.WriteLine("NO"); 
                return; 
            } 
            List<int[]> kb = isright(b); 
            if (kb.Count == 0) 
            { 
                Console.WriteLine("NO"); 
                return; 
            } 

            foreach (int[] kaa in ka) 
            { 
                foreach (int[] kbb in kb) 
                { 
                    int temp; 
                    int a1 = kaa[0], a2 = kaa[1]; 
                    int b1 = kbb[0], b2 = kbb[1]; 
                    if (a1 > a2) 
                    { 
                        temp = a1; a1 = a2; a2 = temp; 
                    } 
                    if (b1 > b2) 
                    { 
                        temp = b1; b1 = b2; b2 = temp; 
                    } 

                    if (a1 * b2 == a2 * b1) 
                    { 
                        if (a1 != b2) 
                        { 
                            Console.WriteLine("YES"); 
                            Console.WriteLine("0 0"); 
                            Console.WriteLine(a2 + " " + a1); 
                            Console.WriteLine(-b1 + " " + b2); 
                            return; 
                        } 
                        else if (a2 != b1) 
                        { 
                            Console.WriteLine("YES"); 
                            Console.WriteLine("0 0"); 
                            Console.WriteLine(a1 + " " + a2); 
                            Console.WriteLine(-b2 + " " + b1); 
                            return; 
                        } 
                    } 
                } 
            } 
            Console.WriteLine("NO"); 
        } 
        List<int[]> isright(int a) 
        { 
            List<int[]> ans = new List<int[]>(); 
            for (int i = 1; i <= a; i++) 
            { 
                for (int j = 1; j <= a; j++) 
                { 
                    if (i * i + j * j == a * a) 
                    { 
                        ans.Add(new int[] { i, j }); 
                    } 
                } 
            } 
            return ans; 
        } 
    } 

} 

main