题目链接:http://codeforces.com/contest/1058/problem/D
题目大意:输入n, m,k,如果能够为n, 宽为m的矩形中找到三个点,这三个点形成的三角形的面积为(n*m)/k,如果能。输出YES并且输出三个点的坐标。如果不能输出NO。

思路:首先可以证明:在矩形中的三角形都可以转化成底边在x轴,高在y轴的直角三角形
ab/2=nm/k
因为0<=a<=n,0<=b<=m
所以k>=2并且(ab=2nm)%k==0那么就一定能够找到这样的三角形。
假如s=(2nm),那么我们要找到a,b;
因为1≤n,m≤1e9,当时这里没有优化好,用了纯暴力枚举,T了。

优化:因为a<=n, b<=m;
所以在枚举a时希望满足条件(a<=n)的a值尽量大,这样b尽量小。b就取得最小值。如果最小的b值都>m,那么就枚举满足条件(b<=n)的b值尽量大。因为一定能够找到这样的三角形。所以其中一个一定满足。

现在就是怎么快速找到满足条件(a<=n)的a的最大值。这个时候a<=n,因为b=s/a;b为整数,那么s%a== 0.
如果循环枚举a。那么复杂度O(n),n<=10^9。
因为s=2nm所以s%n==0,因为s%a并且a<=n,所以n%a ==0。

那么条件为s%a ==0。n%a ==0并且a<=n。
所以a=gcd(n,s)。

思考:gcd真是个好东西。用的很巧妙

#include<bits/stdc++.h>
using namespace std;

int main()
{
    long long n, m, k;
    long long s;
    long long s1;
    long long s2;
    scanf("%lld%lld%lld",&n,&m,&k);
    s=n*m*2;
    if(s%k==0&&k>=2)
    {
        printf("YES\n");
        s/=k;
        long long a, b;

        long long m1=__gcd(s, n);
        long long m2=__gcd(s, m);

        if(s/m1<=m)
            a=m1, b=s/m1;
        else if(s/m2<=n)
            a=s/m2, b=m2;

        printf("0 0\n");
        printf("%lld 0\n",a);
        printf("0 %lld\n",b);
    }
    else
        printf("NO\n");

    return 0;
}